几何扫描线与矩形面积并 (Sweep-Line & Rectangle Area)¶

扫描线算法（Sweep-Line Algorithm） 是计算几何与高维离散化问题中最具威力的通用算法之一。

其核心思想是：“降维打击” —— 想象一条垂直于坐标轴的扫描线（如平行于 Y 轴的竖直线）从左向右均匀扫过整个平面。二维平面内的静态几何图形（矩形、线段、多边形），在扫描线上被投影为一维线段。通过捕捉扫描线与几何图元相交或脱离的关键离散事件（Events），二维面积或相交问题被巧妙转化为一维区间动态维护问题。

1. 扫描线算法核心哲学与事件模型¶

1.1 事件驱动模型 (Event-Driven)¶

对于由 \(n\) 个轴对齐矩形 \([x_1, y_1, x_2, y_2]\) 组成的问题：

每个矩形产生两条垂直边：
入边（左边界 \(x_1\)）：在此处扫描线进入矩形，区间 \([y_1, y_2]\) 被加入活跃集合（权值 \(+1\)）；
出边（右边界 \(x_2\)）：在此处扫描线离开矩形，区间 \([y_1, y_2]\) 从活跃集合中移除（权值 \(-1\)）。
将所有 \(2n\) 条垂直线段按 \(X\) 坐标从小到大排序，构成有序事件队列。

扫描线从左向右扫描过程：
  Y ^
    |       +-------+ (x2, y2)
    |       |       |
    |   +---|---+   |
    |   |   |   |   |
    |   +---|---+   |
    |       +-------+
    +-------------------> X
       x1  x1' x2  x2'
        |   |   |   |
      扫描线依次跨越离散 X 坐标

1.2 面积积分累加¶

相邻两个离散事件的横坐标为 \(x_{i}\) 和 \(x_{i+1}\)：

在区间 \([x_i, x_{i+1}]\) 内，所有矩形在 Y 轴上的有效覆盖总长度保持不变，设为 \(L\)；
这一微元切片贡献的面积为：

\[ \Delta \text{Area} = L \times (x_{i+1} - x_i) \]

最终总面积为所有切片面积之和：\(\text{Total Area} = \sum \Delta \text{Area}\)。

2. 矩形面积并 (LeetCode 850 模型)¶

2.1 坐标离散化 + 扫描线¶

当矩形数量 \(N \le 1000\) 时，可以直接使用离散化扫描线解决。

算法流程：¶

收集与离散化：
提取所有矩形的横坐标 \(x_1, x_2\)，排序去重得到有序数组 \(X\)；
提取所有矩形的纵坐标 \(y_1, y_2\)，排序去重得到有序数组 \(Y\)；
事件排序：
将所有矩形垂直边建模为事件 (x, y1, y2, type)，其中 \(type = +1\) 表示进入，\(type = -1\) 表示离开；
按横坐标 \(x\) 升序排序；
动态维护 Y 轴覆盖长度：
扫描线移动时，使用差分数组或线段树维护当前 Y 轴上每个基本区间的被覆盖层数 cover_count；
统计当前总覆盖长度 \(L\)，乘以 \(\Delta x\)，累加至总面积。

2.2 线段树维护区间被覆盖长度 (O(N log N) 工业级模板)¶

当数据规模较大时，线段树是维护 Y 轴覆盖长度的标准工具：

线段树每个节点维护：
cnt：当前区间被完全覆盖的次数；
len：当前区间内被覆盖的实际几何长度；
免除下传标记（Lazy Tag）技巧：
因为每个矩形的入边和出边成对出现，且修改总是覆盖整个线段树叶子区间；
若 cnt > 0，当前区间的被覆盖长度直接等于区间全长；
若 cnt == 0，当前区间的被覆盖长度等于左右儿子的被覆盖长度之和（叶子节点为 0）。无需下推 lazy tag，代码极其精简！

3. 完美矩形验证 (LeetCode 391)¶

问题：给定若干小矩形，判断它们是否恰好完美无缝且无重叠地拼成一个大矩形。

3.1 完美矩形的两大充要条件¶

一个矩形集合能够完美拼成大矩形，当且仅当满足以下两条几何不变量：

精确面积守恒：所有小矩形的面积之和，严格等于所有小矩形构成的最小外接矩形（大矩形）的面积：

\[ \sum_{i=1}^n \text{Area}(rect_i) = (\max X - \min X) \times (\max Y - \min Y) \]

顶点奇偶消除律（顶点哈希）：
考察所有小矩形的 \(4n\) 个顶点：
- 若四个矩形在某内部点相交，该点出现 4 次；
- 若两个矩形在某边上接触，该点出现 2 次；
- 若点是整个大矩形的四个外角顶点，该点必须恰好且只能出现 1 次；
- 所有其他内部顶点与边界接触点，在集合中出现的总次数必须为偶数！
用哈希集合 unordered_set 记录所有顶点坐标：遍历所有小矩形的 4 个顶点，若该点已在集合中则将其移除（异或抵消），否则插入；
最终哈希集合中必须且只能剩下恰好 4 个顶点，且这 4 个顶点必须是大矩形的 4 个外角！

4. LeetCode 经典真题精选与深度精析¶

LeetCode 850 - 矩形面积 II (Rectangle Area II) 困难
提示

离散化扫描线 + 线段树维护区间长度。
- 详见本文第 2 节。
- 坐标范围巨大（\(10^9\)），必须先对 Y 坐标离散化。
- 将矩形拆解为左右两条垂直边，按 X 坐标升序遍历。
- 线段树维护 Y 轴覆盖长度，每次跨越 \(\Delta X\) 累加面积取模。时间复杂度 \(\mathcal{O}(N \log N)\)。
LeetCode 391 - 完美矩形 (Perfect Rectangle) 困难
提示

面积守恒 + 顶点异或消除双重验证。
- 详见本文第 3 节。
- 累加所有矩形面积，同时记录全局 \(\min X, \max X, \min Y, \max Y\)。
- 哈希集合统计 \(4N\) 个顶点出现奇偶性。
- 验证：面积必须等于大矩形面积，且集合中最终留存的点必须且仅为 4 个外角。严格 \(\mathcal{O}(N)\) 时间与空间。