1. 序言

求矩形面积并指的是给你n个矩形的顶点坐标(矩形的边必然平行于坐标轴),求它们所覆盖的总面积(重叠覆盖的面积只算一次覆盖)。
暴力枚举矩形的话如果n较大显然会超时。这时候我们就需要一种新算法:扫描线。这种算法求矩形面积并的复杂度是nlogn的。

2. 例题

HDU - 1542 Atlantis 传送门= ̄ω ̄=
题目大意:给出n个矩形(矩形顶点左边可能为小数)1<=n<=100,求这些矩形覆盖的面积大小(多次覆盖同一个地方只算一次覆盖),即求这些矩形的面积并。含多组数据

3. 详解

典型的求矩形面积并的题目。
对于题目的样例:

2
10 10 20 20
15 15 25 25.5
0

它的图像是这样的:

答案便是下图中黄色部分的面积:

其中有一个重叠部分。

我们现在要用扫描线解决这张图。
首先我们对每个竖线的横坐标进行离散化:

(上图中黑线表示了一个纵轴,黑线旁边的那个数字表示这个纵轴的横坐标。)

这样我们就等于把数据变成了:

2
1 10 3 20
2 15 4 25.5
0

注意上面数据中的粗体数字,表示横坐标是经过离散化的。

为什么要离散化呢?因为啊,你不离散化,把小数的横坐标变成整数,你后面怎么线段树维护啊?

我们把离散化以后的坐标存到一个hash表里,hash[a]表示排第a个的横坐标的值是多少。比如上面那个数据中,hash[1]=10,hash[2]=15,hash[3]=20,hash[4]=25.5。hash的同时要记得去重。

这样我们就通过这些离散化以后的横坐标把整个总区间分成了cnt-1个区间,其中cnt表示去重以后横坐标的个数,上面的样例中,cnt=4。如图:

第a个区间的左端点的横坐标是h[a],右端点的横坐标是h[a+1]。

于是我们对于这cnt-1个区间建立线段树。
为什么要建立线段树呢?我们等下讲。

这时候我们的重头戏来了:扫描线!
我们取出每个矩形的上边和下边,下边标为红色,上边标为蓝色。如图:

然后我们的扫描线从下向上扫描,此时每个区间的被覆盖次数都为0,如图:

好,我们的扫描线向上移动的时候碰到了一个下边!这个下边对应线段树上的区间1和区间2,因为这是个下边,所以这两个区间在线段树上的“被覆盖次数”都+1变为了1.

我们保存一下这个扫描线的位置(纵坐标),然后扫描线继续向上移动到下一条边。。。好,扫描到了!如图所示:

上一条保存的扫描线到当前扫描线的距离为h=15-10=5,而总区间被覆盖了的区间有区间1、2,这两个区间的总长度是(20-10=10),所以图中黄色部分的面积为10h。那么我们让答案加上10h=50。当前答案为50。
又因为这是一条下边,所以区间2,3的被覆盖次数+1,如图所示:

扫描线继续向上走,这次碰到的边是一条上边。如图:

当前线段树被覆盖的区间有区间1、2、3,所以被覆盖长度为(25-10=15),h=20-15=5,所以黄色部分的面积为15h=75,答案加上75,当前答案为125。
因为这是一条上边,所以区间1、2的被覆盖次数-1,如图所示:

扫描线继续上移,碰到一条上边。如图:

当前线段树被覆盖的区间有区间2、3,所以被覆盖长度为(25-15=10),h=25.5-20=5.5,所以黄色部分的面积为10h=55,答案加上55,当前答案为180。

至此我们已经得到了正确答案:180,而因为当前这条边是上边,所以区间2、3被覆盖次数-1,所以所有区间的覆盖次数全部为0了。

回头看整个过程,其实就是把这个不规则的矩形面积并分成了这几个部分:

这里并没有体现出线段树的用处。显然这些操作都是区间加减:遇到下边+1,遇到上边-1,用线段树可以做到logn。

这里的区间覆盖不需要打懒惰标记。为什么呢?因为很显然,每个下边都有与之对应的上边,它显然不会被比它的长度小的上边给清除。而如果有比它长的上边,也一定有和那个上边对应的下边还存在。所以用那个上边清除下边的时候,一定会先递归到那个更长的下边,还没有递归到它就停止递归了。所以每个上下边是一一对应的,无需下传标记等。

至于每个区间的被覆盖长度len,取决于它的被覆盖次数x。如果x>0,说明它被整体覆盖,len就等于该区间长度。如果x=0,那len等于它的左儿子区间的len+右儿子区间的len。

还有扫描线的上移,就是把那些上边、下边按照纵坐标大小从小到大排序即可。

其实扫描线是从下向上,或者从左到右,还是别的方向,都是一个原理,改一下离散化、区间加减就行了。

那么这道题的代码就是: