解題說明
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)。適合矩形數量很大的情況。
-
容斥原理:直接計算所有矩形面積之和,減去兩兩交集,加上三三交集...但矩形數量多時,交集的組合數爆炸,不如掃描線高效。僅適合矩形極少的情況。
延伸思考
- 如果要求的是所有矩形覆蓋的周長而非面積呢?
- 如果矩形可以旋轉(不一定軸對齊),這個問題會變得多困難?
- 如何擴展到三維空間中多個長方體的體積聯集?