矩形并

给定若干轴对齐矩形,求并的面积和周长;按 x 扫描,用线段树维护 y 方向覆盖长度与连通分量数。

标签 计算几何 / 扫描线 / 线段树 / 矩形并

题目描述

给定 𝑛 个轴对齐矩形

𝑅𝑖=[𝑎𝑖,𝑏𝑖)×[𝑐𝑖,𝑑𝑖),𝑖=1,…,𝑛.

求它们的并的面积和周长。

1≤𝑛≤105,0≤𝑎𝑖<𝑏𝑖≤109,0≤𝑐𝑖<𝑑𝑖≤109,坐标均为整数。

输出两个整数:并的面积和周长。

题解

把 𝑦 方向的所有端点 𝑐𝑖,𝑑𝑖 排序,分成原子区间 𝒜︀。每个原子是一个小区间,矩形并的覆盖状态在原子内不变。令

𝐺=ℤ(𝒜︀).

取事件 𝑒𝑖+:在 𝑎𝑖 处加入 𝐽𝑖=[𝑐𝑖,𝑑𝑖);以及 𝑒𝑖−:在 𝑏𝑖 处删除 𝐽𝑖。按 𝑥 升序排列,同一 𝑥 的插入事件先于删除事件。状态 𝑠∈𝐺 记录每个原子的覆盖重数,初态 𝑠0=0,转移为

𝑈(𝑒𝑖+,𝑠)=𝑠+𝑒𝐽𝑖,𝑈(𝑒𝑖−,𝑠)=𝑠−𝑒𝐽𝑖.

把不同事件坐标记为 𝑥1<…<𝑥𝑁,𝑠𝑗 为处理完 𝑥𝑗 处所有事件后的状态。相邻坐标之间状态不变。记

𝐿(𝑠)=∑𝐴∈𝒜︀[𝑠(𝐴)>0]|𝐴|

为覆盖总长度,𝐶(𝑠) 为被覆盖原子的连通分量数。

面积是

𝐴=∑𝑗=1𝑁−1𝐿(𝑠𝑗)(𝑥𝑗+1−𝑥𝑗).

周长分两部分:

  • 竖直边:每个覆盖分量贡献两条竖直边,

    2∑𝑗=1𝑁−1𝐶(𝑠𝑗)(𝑥𝑗+1−𝑥𝑗);
  • 水平边:覆盖长度在事件点处的总变化,

    ∑𝑗=1𝑁|𝐿(𝑠𝑗)−𝐿(𝑠𝑗−1)|,

    其中 𝐿(𝑠0)=0。

同一 𝑥 上插入先于删除,处理完该坐标的全部事件后再比较覆盖长度,避免水平边重复计数。

用线段树维护 𝐿(𝑠) 和 𝐶(𝑠)。每个节点记录区间覆盖次数、覆盖长度、覆盖分量数、左右端点是否被覆盖。区间加减时更新覆盖次数并合并左右儿子;根节点给出 𝐿(𝑠) 和 𝐶(𝑠)。每个事件是一次区间加,扫描时累加面积与周长。

正确性

面积按 𝑥 切片:[𝑥𝑗,𝑥𝑗+1) 上的并截面长度是 𝐿(𝑠𝑗),乘以宽度后求和即为面积。

周长中,竖直边来自每个 𝑥 区间内覆盖集合的各个连通分量;水平边来自覆盖长度函数在事件坐标处的跳变。把同一 𝑥 的事件一起处理,跳变量就是处理前后的覆盖长度差,因此每条水平边恰好计一次。

复杂度

每个事件对应一次线段树区间加,单次 𝑂(log𝑛)。共有 2𝑛 个事件,时间 𝑂(𝑛log𝑛);空间 𝑂(𝑛)。

源码位置