扫描线
引入
矩形面积并
给出 $n$ 个边平行于坐标轴的矩形，求它们的面积并。
扫描线
将问题拆解成时间序列关键点，可以想象一条线在平面上扫过，在一些特定的位置这条线上对应的状态会发生变化。
两要素：
- 时间序列：状态发生变化的关键点。
- 维护当前时间状态的数据结构。
引入的解
两要素：
- 时间序列：每个矩形的上下边
- 数据结构：线段树（区间修改，查询覆盖的区间长度）
应用
判断 $n$ 条线段中是否存在有交点的线段
朴素做法：$O(n^2)$。
尝试扫描线，一条垂直于 $x$ 轴的线从左向右扫。
关键点：线段的端点（左端点加入，右端点删除）
考虑对于每一个时间点的竖线，把所有与之相交的线段，按纵坐标（y）升序排序。那么两条有交点的线段的先后顺序会在某一时刻发生变化。
具体而言，其先后顺序发生变化的情况有两种：
- 新加入一条线段，与这条线段相邻的两条线段先后顺序发生变化。
- 删除一条线段，原本被这条线段隔开的两条线段先后顺序发生变化。
使用 set 维护。
时间复杂度：$O(n\log n)$。
细节：
- 一个关键点上有多个操作的情况（多条线段共端点）
- 线段与扫描线平行的情况（平行 y 轴）
面积并问题
对于部分问题，扫描线并不是最优解。
三角形面积并
法一：扫描线
- 关键点：三角形顶点，交点。
- 关键点之间的面积可用梯形面积公式计算。
时间复杂度：$O(n^3)$
法二：轮廓法
三角形的并本质上是多边形，如果能找到这个多边形的轮廓，可用直接使用求多边形面积的算法求得面积并。
对于每一条边，求出它与其它所有三角形的交点，找到没有包含在任何三角形内部的部分。
时间复杂度：$O(n^2)$