解題說明
Rectangle Area II
題目描述： 給定若干個軸對齊的矩形，每個矩形由左下角 (x1, y1) 和右上角 (x2, y2) 定義。計算所有矩形覆蓋的總面積（重疊部分只計算一次）。結果對 10^9+7 取模。
解題思路：
- 座標壓縮 + 掃描線：將所有 x 座標和 y 座標分別離散化。
- 對 y 軸方向進行掃描：將矩形拆成「進入事件」（下邊）和「離開事件」（上邊）。
- 按 y 座標排序所有事件。從下往上掃描，在每個 y 區間內，計算 x 軸上被覆蓋的總長度。
- 被覆蓋長度 × y 區間高度 = 該區間的面積貢獻。
- x 軸上的覆蓋長度可以用計數陣列或掃描來計算：對每個壓縮後的 x 區間維護覆蓋次數，覆蓋次數 > 0 的區間計入長度。
C++ 解法
複雜度分析
時間複雜度：O(n^2 log n) — n 為矩形數量。座標壓縮後最多 2n 個 x 區間，每個事件需遍歷 x 區間。排序 O(n log n)
空間複雜度：O(n) — 存儲壓縮座標和事件
虛擬碼
1. Collect all unique x-coordinates, sort and deduplicate 2. For each rectangle, create two events: - Open event at y1 (bottom edge): mark x-interval [x1, x2] - Close event at y3 (top edge): unmark x-interval [x1, x2] 3. Sort events by y-coordinate 4. Sweep from bottom to top: a. For current y, compute covered x-length from count array b. Area contribution = covered_x_length * (curY - prevY) c. Process all events at curY: increment/decrement count for x-intervals d. Update prevY = curY 5. Return total area mod 10^9+7
其他解法
-
線段樹優化掃描線：用線段樹維護 x 軸上的覆蓋長度，每次事件更新為 O(log n)，整體時間複雜度降為 O(n log n)。適合矩形數量很大的情況。
-
容斥原理：直接計算所有矩形面積之和，減去兩兩交集，加上三三交集...但矩形數量多時，交集的組合數爆炸，不如掃描線高效。僅適合矩形極少的情況。
延伸思考
- 如果要求的是所有矩形覆蓋的周長而非面積呢？
- 如果矩形可以旋轉（不一定軸對齊），這個問題會變得多困難？
- 如何擴展到三維空間中多個長方體的體積聯集？