【学习笔记】扫描线

【别急，我也不会，没写完】

• 定义：
• 例题（解释）：

定义：

如图：

（图片来源：oiwiki）

像这样的一条线在图上扫描时，便是扫描线。

（呃呃和没说没有任何区别呢）

因此可见扫面线往往是求矩形面积并集或周长并集的好工具，当然，也可以运用在二维图中。

当然它不止可以从上往下扫，还可以从左往右扫：

（当然自己画的图可能丑一些，我解释一下，那个紫色的是扫描线）

如果说我们要求这个两个矩形的并面积怎么求？

当然你可能是啊啊\(Sonnety\)真是个笨蛋呢这我直接容斥：\(S_1+S_2-S_1\times S_2\)。

但是要是数据范围很大呢？多步容斥？

这下不得不跟您谈一谈我们内存及其优秀的且很快的 \(O(nlogn)\) 算法了。

例题（解释）：

我们跟着例题说这个：

题目链接

怎么求这两个矩形的面积并？

求三个小矩形面积相加嘛。

怎么求这三个矩形的面积？

宽是两条扫描线的之间的 \(x\) 差值，长是求边嘛。

我们把每条扫描线与矩形边重合部分的左右端点记录一下， \(y\) 轴高度记录一下就可以了：

\(S=\) 两条扫描线之间高度差\(\times\)扫描线覆盖长度

如何维护 \(x\) 长度？

选择桶来维护扫描线上的 \(x\) 是否被覆盖，显然是有很多问题的：

• Q：如果 \(x\) 不一定是非负整数？

• A：如果 \(x\) 是浮点数或者较大（甚至不是非负数），我们需要选择离散化，使得下标对应实际的 \(x\)。

• Q：时间复杂度？

• A：线段树优化。

• Q：空间复杂度？

• A：存储左右端点的 \(x\) 坐标。

什么什么什么，等等，线段树优化？

为什么能够线段树优化？

我们把每一条垂直于 \(x\) 轴的竖边提取出来，然后把他们延伸到 \(y\) 轴上，你看，这不就把 \(y\) 轴分割成了线段？

因此，我们设 \([1,2]\) 是我们第一个被切割出的长方形横边长度，以此类推，\([l,r]\) 就是我们需要维护的区间：

• 区间的左右端点 \(l,r\)。

• 区间被覆盖的次数。

• 区间被横边覆盖的长度。

首先，当我们遇到一个横边的时候，区间就肯定被覆盖了至少 \(1\) 次。

其次，该区间被整体覆盖，覆盖的长度即区间长度。

最后，我们统计线段树根节点的长度标记，乘两条横边之间高度差就得到了一部分的面积。