矩形并
给定若干轴对齐矩形,求并的面积和周长;按 x 扫描,用线段树维护 y 方向覆盖长度与连通分量数。标签 计算几何 / 扫描线 / 线段树 / 矩形并
题目描述
给定 个轴对齐矩形
求它们的并的面积和周长。
,,,坐标均为整数。
输出两个整数:并的面积和周长。
题解
把 方向的所有端点 排序,分成原子区间 。每个原子是一个小区间,矩形并的覆盖状态在原子内不变。令
取事件 :在 处加入 ;以及 :在 处删除 。按 升序排列,同一 的插入事件先于删除事件。状态 记录每个原子的覆盖重数,初态 ,转移为
把不同事件坐标记为 , 为处理完 处所有事件后的状态。相邻坐标之间状态不变。记
为覆盖总长度, 为被覆盖原子的连通分量数。
面积是
周长分两部分:
竖直边:每个覆盖分量贡献两条竖直边,
水平边:覆盖长度在事件点处的总变化,
其中 。
同一 上插入先于删除,处理完该坐标的全部事件后再比较覆盖长度,避免水平边重复计数。
用线段树维护 和 。每个节点记录区间覆盖次数、覆盖长度、覆盖分量数、左右端点是否被覆盖。区间加减时更新覆盖次数并合并左右儿子;根节点给出 和 。每个事件是一次区间加,扫描时累加面积与周长。
正确性
面积按 切片: 上的并截面长度是 ,乘以宽度后求和即为面积。
周长中,竖直边来自每个 区间内覆盖集合的各个连通分量;水平边来自覆盖长度函数在事件坐标处的跳变。把同一 的事件一起处理,跳变量就是处理前后的覆盖长度差,因此每条水平边恰好计一次。
复杂度
每个事件对应一次线段树区间加,单次 。共有 个事件,时间 ;空间 。