扫描线 » 老官童鞋gogo的博客

学习扫描线，你需要先学习线段树和离散化

扫描线简介

扫描线是一种求矩形面积并/周长的好方法，同样的，它可以延伸到很多地方。注意，扫描线并不是一条存在的线，是在解释算法时的帮助我们更好理解的线。

扫描线原理

现在在平面直角坐标系中有$n$个矩形，它们相互重叠在一起，求出所有矩形占有的面积（重叠部分只算一次）。如果采用暴力枚举每一个点，那么空间与时间都会爆炸，如果利用容斥原理，先将所有的矩形面积相加，最后减去重叠的部分，但是这种方法也很麻烦，也会超时。

但是我们有一种很优秀的算法——扫描线。假设有一条扫描线从一个图形的下方扫向上方（或者左方扫到右方），那么通过分析扫描线被图形截得的线段就能获得所要的结果。该过程需要线段树来加速。如果文字不便于理解，看图：

扫描线的实现

如上图，我们可以把整个矩形分成如图各个颜色不同的小矩形。每一个小矩形的面积相加就是总面积。计算每一个小矩形的面积需要知道每一个小矩形的高与长。

这个小矩形的高就是我们扫过的距离。首先将每一条与$x$轴平行的边排序，从下往上枚举，每相邻的两条边$y$坐标的差值就是扫描线扫过区域的高。

现在只剩下每一个小矩形的长度没有处理了，因为矩形之间存在重叠，所以这里的长度不是矩形长度之和，我们可以通过暴力枚举左端点到右端点，计算长度，但是这样太浪费时间了。我们可以通过线段树加速，我们将每条与$y$轴平行的线段排序、离散化，去除$x$坐标相同的边，将排序之后的坐标放入一个数组中，记为$x[]$。如图：

那么我们每一个小矩形的长度就可以表示出来了，例如从下往上数第一个矩形它的面积就是$x[3]$和$x[2]$之间的实际距离与第一条红线与第二条红线之间的实际距离相乘。为了不断更新小矩形的长，我们把它放到线段树中，如图：

当扫描线扫描到一条新线段的时候，我们就去更新线段树，比如扫到最下面这条线段的时候，线段树节点$1,2$就会被更新，再往下扫描到第二条线段，线段树中节点$1,2,3,5,6$就会被更新。不难看出，线段树所维护的左右节点实际上是线段的编号，另外维护线段覆盖长度和权值。这样扫描线扫到有权值的部分就有我们要计算的面积，那么就更新线段覆盖长度。

但是当我们只说了要记录，没有说应该怎么记录，我们应该如何判断这条线段后面究竟有没有被覆盖的面积呢？因为每一个矩形都有上底和下底，在扫描线从下往上扫的时候，总是先遇到一个矩形的下底，在遇到矩形的上底，然后这一个原矩形就被扫描过了。所以，扫描过程中，我们需要将权值放在线段树中，下底标为$1$，上底标为$-1$。这样一来，如果线段树上节点的权值不为$0$，就说明这条线段的背后存在着要被计算的面积。

总结一下：如果题目要求离散化，就需要在线段树中存两个值，一个用来判断这条线的背后有没有需要计算的面积，另一个值用来记录离散化之前，它所表示线段的长度。如果没有离散化，就不需要记录第二个值。

如果你对上面的文字不是太理解的话，看看下面的代码和注释吧！

代码

#include<iostream>//从一开始到63行都是”恶臭“缺省源，不要害怕。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long uLL;
typedef __int128 int128;
typedef unsigned __int128 uint128;
typedef long double Ld;
#define reg register;
#define space putchar(' ')
#define enter putchar('\n')
#define PI 3.14159265358979323846
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 1000000000
#define INF 1000000000000000000
#define N 1010
#define M 10000010
namespace Fast{
	template<typename T>inline void read(T &x){
		x=0;bool f=false;char c=getchar();
		while(c<'0'||c>'9'){if(c=='-')f=true;c=getchar();}
		while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(f)x=~x+1;
	}
	template<typename T>inline void print(T x){
		int s[65],top=0;
		if(x<0)putchar('-'),x=~x+1;
		while(x)s[++top]=x%10,x/=10;
		if(!top)s[++top]=0;
		while(top)putchar(s[top--]+'0');
	}
	template<typename T,typename...Args>inline void read(T &x,Args&...others){
		read(x),read(others...);
	}
	template<typename T,typename...Args>inline void print(T x,Args...others){
		print(x),space,print(others...);
	}
	const double eps=1e-7;
	template<typename T>inline T Abs(T x){return x>0?x:-x;}
	template<typename T>inline T Max(T x,T y){return x>y?x:y;}
	template<typename T>inline T Min(T x,T y){return x<y?x:y;}
	template<typename T>inline T Fabs(T x){return x>eps?x:-x;}
	template<typename T>inline T Fmax(T x,T y){return x-y>eps?x:y;}
	template<typename T>inline T Fmin(T x,T y){return x-y<eps?x:y;}
	template<typename T>inline void addmod(T &x,T p){if(x>=p)x-=p;}
	template<typename T>inline void submod(T &x,T p){if(x<0)x+=p;}
}
using namespace Fast;//如果你对上面的缺省源感兴趣或者你想使用这个缺省源（真的很快很方便！），到主页侧边栏《代码模板》领取
struct Node{//第一个结构体记录每一条与x轴平行的线段的信息。因为这里是从下往上扫的扫描线
    LL l,r,h;//每一条线段的左端点坐标 右端点坐标 纵坐标。
    int val;//val的意义就是在下底使这一个线段权值加1 表示扫描线向下扫的时候保证这条线段的下方是覆盖的，遇到上底时权值-1，也就是覆盖结束了。对于整个平面，扫描线所加的面积就是扫过的并且有权值的位置。
    inline bool operator<(const Node &k)const{
        return h<k.h;
    }//重载运算符，方便使用STL排序，使得纵坐标小的线段，也就是每个矩形的下底优先被扫描线读到。
}seg[M];
struct Node2{//第二个结构体记录线段树的相关信息。
    LL sum,len;//sum是线段树节点的权值，也就是被覆盖的次数。注意，由于是求面积并，所以被覆盖一次还是两次并没有区别，只是有权值和没权值的区别，有权值的线段 在扫描线扫过的时候就会计算面积 否则就不会计算面积。len表示线段树节点所表示的横向线段的长度。
}tree[M];//空间要开足够大，一个线段树四倍，最好开到八倍会好一点。
LL x[M];
LL n,X1,X2,Y1,Y2,ans;
void pushup(int i,int l,int r){
    if(tree[i].sum){//这就是上面所说的 只有被覆盖和没被覆盖的区别。
        tree[i].len=x[r+1]-x[l];//如果线段被扫描线扫到了，则更新扫到的线段长度。
    }
    else{
        tree[i].len=tree[i<<1].len+tree[i<<1|1].len;//如果没被扫到 则从以前扫过的线段更新。
    }
    return;
}
void change(int i,int nl,int nr,int l,int r,int k){//当扫描线扫到一条线段，执行此操作，nl、nr分别表示当前线段树节点的左右端点，l、r分别记录线段的左右端点坐标，k代表这是下底还是上底。
    if(l>=x[nr+1]||r<=x[nl]){//要更新的线段不属于这个线段树节点，这是一个剪枝。
        return;
    }
    if(l<=x[nl]&&r>=x[nr+1]){
        tree[i].sum+=k;//更新，如果是下底 那么sum就有了值，代表扫描线往上的地方需要计算面积。如果是上底，那么sum不一定没有值，只是减少，代表它对应的矩形面积计算完毕。
        pushup(i,nl,nr);
        return;
    }
    //由于有剪枝，我们就不用判断应不应该向左右儿子下传了，直接修改子树就好了。
    int mid=(nl+nr)>>1;
    change(i<<1,nl,mid,l,r,k);
    change(i<<1|1,mid+1,nr,l,r,k);
    pushup(i,nl,nr);
    return;
}
int main(){
	read(n);
    for(int i=1;i<=n;i++){
        read(X1,Y1,X2,Y2);
        x[(i<<1)-1]=X1,x[i<<1]=X2;
        seg[(i<<1)-1]=(Node){X1,X2,Y1,1};//记录线段的信息
        seg[i<<1]=(Node){X1,X2,Y2,-1};
    }
    n<<=1;//线段数是矩形数二倍，因为每个矩形都有上底和下底。
    sort(seg+1,seg+1+n);//按照横向线段纵坐标升序排序。方便我们从下往上扫
    sort(x+1,x+1+n);//相同的横坐标我们只需要一次，原因看上面的图
    int cnt=unique(x+1,x+1+n)-x-1;//因此通过离散化来确定不同横坐标的数量
    //这里不需要建树，因为树本来是空的，并且我们会将线段树左右端点放到函数参数中
    for(int i=1;i<n;i++){//最后一条边就不需要更新了，因为后面就没有覆盖了的面积了。
        change(1,1,cnt-1,seg[i].l,seg[i].r,seg[i].val);//这里cnt要-1，因为cnt表示的是横坐标的点，而线段树存储的是区间，具体看上图。
        ans+=tree[1].len*(seg[i+1].h-seg[i].h);//k
    }
    print(ans);
	return 0;
}