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