扫描线

· · 算法·理论

扫描线

扫描线是一种用来求出多个矩形的面积并的算法，在此之前，你需要学会线段树。

何为面积并？就是把几个矩形放到一个平面中，可能会有重复覆盖的区域，求出所有矩形的覆盖面积之和（重复覆盖的区域只算一次）。

我们来看下边这张图：

要求出这些矩形的面积并，我们首先可能会想到容斥，但是当矩形数量很多的时候，我们就不好用容斥来想了。

我们再看下边这张图：

我们用若干条线段，将整个图形分成了几个矩形，这些矩形没有相互覆盖，所以原矩形的面积并其实就是现在矩形的面积之和。

接下来思考如何计算这些矩形面积之和，我们只要知道当前线被矩形截成的长度，再乘上向上扫过的长度，就是这一部分的面积。

考虑维护线段被矩形截成的长度，我们给每个矩形下边的那条边上的点都加上 1，上边的每个点都减去 1，在从下往上扫的过程中，那条扫描线总是会先碰到每个矩形的下边，再碰到上边，可以使扫描线所得到的长度永远非负。

接下来我们把每条线段的左右端点对应到 x 轴上，会把 x 轴分成若干个区间，比如上边的例子就长下边这样

这样的话，我们就可以用线段树维护每个区间，我们需要维护的信息有：区间的左右端点、这条线段被几个矩形覆盖以及这条线段被整个图形所截的长度是多少。

在建树的时候，我们会发现一个问题，我们平时写的线段树，两个区间是没有重合部分的，但是在这里我们要维护线段，也就是说一个节点的左儿子的右端点与右儿子的左端点是重合的，因为线段是连续的，总不能一条线段因为在两个节点都有一部分就把它拆开吧。所以我们可以将每个区间实际右端点加上 1 就解决了这个问题。

当然，由于这个横坐标可能很大，我们需要对其进行离散化。

注意：用万能头或者<cmath>库的时候，不要使用x1，x2，y1，y2这类变量名，否则可能会出现意想不到的错误。

代码实现

#include <bits/stdc++.h>
#define ll long long
#define mkp(x,y) make_pair(x,y)
using namespace std;
const int N=1e6+5;
const int M=1e6+5;
int n;
ll X[N<<1],ans;
struct ScanLine
{
    ll l,r,h;
    int mark;
    bool operator < (const ScanLine &rhs){
        return h<rhs.h;
    }
}line[N<<1];
struct SegmentTree
{
    int l,r,sum;//sum表示被几个矩形覆盖
    ll len;//len表示线段被矩形截的长度
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define sum(x) tree[x].sum
    #define len(x) tree[x].len 
}tree[N<<2];
void build(int p,int l,int r)
{
    l(p)=l,r(p)=r;
    if(l==r)return;
    int mid=l+r>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    sum(p)=len(p)=0;
}
void update(int p)//更新线段被矩形截的长度
{
    if(sum(p))//如果被矩形覆盖了
        len(p)=X[r(p)+1]-X[l(p)];//线段长度可以直接计算得出，+1是因为我们修改了右端点的表示
    else
        len(p)=len(p*2)+len(p*2+1);//否则就直接计算儿子的长度之和
}
void change(int p,int l,int r,int d)//这里是更新线段树
{
    if(X[r(p)+1]<=l||X[l(p)]>=r)return;//如果当前节点不在这条线段里就跳过，+1的原因也是我们修改了右端点的表示
    if(l<=X[l(p)]&&r>=X[r(p)+1])//如果当前区间被这条线段完全包含
    {
        sum(p)+=d;//更新被矩形覆盖次数
        update(p);//同时计算被矩形截的长度
        return;
    }
    change(p*2,l,r,d);//递归计算左右子树
    change(p*2+1,l,r,d);
    update(p);//将被截的长度向上传递
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        ll x_1,x_2,y_1,y_2;//注意最好别用x1,x2,y1,y2
        scanf("%lld%lld%lld%lld",&x_1,&y_1,&x_2,&y_2);
        X[i*2-1]=x_1;X[i*2]=x_2;//这里是离散化，存储每个矩形上边和下边的x坐标
        line[i*2-1]=(ScanLine){x_1,x_2,y_1,1};//矩形上边和下边分别有一条线，上边的值为-1，下边为1
        line[i*2]=(ScanLine){x_1,x_2,y_2,-1};
    }
    n<<=1;
    sort(X+1,X+n+1);//将x排序，进行分段
    sort(line+1,line+n+1);//将所有线段按照h从小到大排序
    int tot=unique(X+1,X+n+1)-X-1;//这里去重，防止有重复的段
    build(1,1,tot-1);//由于我们修改了右端点的表示，所以要表示[X[1],X[tot]]这个区间只用到tot-1就可以了
    for(int i=1;i<n;i++)
    {
        ll l=line[i].l,r=line[i].r;
        int c=line[i].mark;
        change(1,l,r,c);//更新线段树
        ans+=len(1)*(line[i+1].h-line[i].h); //答案就是线段长度乘上扫过的高度，由于所有被截的长度都向上传递到了1号节点，故直接用len(1)即可
    }
    printf("%lld\n",ans);
    return 0;
}