Posted on 2011-12-25 16:10
Mato_No1 阅读(383)
评论(0) 编辑 收藏 引用
【本沙茶以前曾经搞过
矩形的面积并、周长并问题，当时几乎是抄神犇代码的，根本木有理解，现在在看了扫描线以后理解一些了】
“扫描线”严格来说不是算法，而是一种思想，它在解决很多几何问题或者矩阵问题中有大用。所谓“扫描线”，就是用一条假想的直线（一般是水平或者竖直的）沿x轴（或y轴）方向扫过整个平面，在此过程中，每当发现有特殊事件（比如插入、删除事件等），就执行这一事件。一般来说，它需要配合数据结构进行加速，常用的数据结构有线段树、平衡树、树状数组、堆、凸多边形集合等。
【1】矩形的面积并和周长并问题：
这个在以前总结的那一篇里面曾经说明过，这里只是补充一下。
对于面积并，可以假想一条水平直线沿y轴正方向扫过整个平面，每当遇到矩形的上下边界，就插入或删除一条线段（上边界为插入，下边界为删除），在每两个相邻上下边界之间得到覆盖面积为：目前插入（尚未删除）的所有线段覆盖的总长度乘以两边界间的距离。显然，求前者需要用离散化（横坐标）+线段树实现。
这里讲一下离散化的步骤和易疵点：首先将要离散化的数据（设为A数组）存储在一个数组B里，然后对B排序（一般是递增排序）、去重（方法：
若B长度为0则不需去重，否则B[0]保留，从B[1]开始，若B[i]>B[i-1]则保留B[i]否则跳过B[i]），得到一个新的数组B0，最后，再对原来的A数组中的每个元素在B0中二分查找，找到其位置即可。显然，对N个数据离散化时间复杂度为O(NlogN)，具体实现时，可不设B0，直接存在B里面（见代码）。易疵的地方主要是B的长度为0的情况。
re(i, n0) B[i] = A[i].x;
qsort(B, n0, sizeof(B[0]), cmp);
n = 1; re2(i, 1, n0) if (B[i] > B[i - 1]) B[n++] = B[i];
re(i, n0) A[i].x = find_x(A[i].x);
其中n0为数据个数，n为去重后的数据个数（也就是离散化后的编号范围，很重要的！），find_x为二分查找过程。
对于周长并可以这样理解：照样是水平直线沿y轴正方向扫过整个平面，照样是遇到矩形的上下边界就插入或删除，这样，周长的水平部分是很好得到的，只要统计每两个相邻上下边界的线段覆盖总长之差即可，对于竖直部分则需要统计被
线段覆盖的端点个数——或者说，需要统计至少作为一条目前插入线段的端点，且木有被任何一条线段内部包含的端点个数（因为只有这些点所延伸下来的竖直线段有可能作为周长的竖直部分）。维护方法：给每个结点设立ss、lbd与rbd，分别表示该结点区间内这种点的个数，以及该线段区间的左右端点是不是这种点。lbd=LCH.lbd; rbd=RCH.rbd; ss=LCH.ss+RCH.ss-2*(LCH.rbd || RCH.lbd)（因为我们需要的是线段树而不是点树，因此其中的每个叶结点表示的实际上是一条单位线段，而不是一个点，这样，LCH区间的右端点与RCH区间的左端点其实是同一个点，如果它们都是这种点，则都不能算，因为被包含在内部了）。例外的是，如果某个结点区间完全被某条插入线段包含，则ss为2，lbd、rbd均为1（这个结果可能不正确，因为可能左右端点被包含在内部，因此，整棵树上只有根结点的ss值是绝对正确的ss值，其余结点都需要特判）。这样，根结点的ss值就是这种点的个数，乘以两相邻上下边界的距离就是之间的竖直部分总长度。
代码：
面积并（HDU1542）周长并（HDU1828）（此外，周长并还有一种更容易理解的算法：就是先求出水平部分总长后，将所有的矩形旋转90度，再求一次水平部分总长，这就是原来的竖直部分总长了）
【2】应用：
PKU2482