二維問題太複雜——固定一個維度，把它變成一連串的一維問題。
掃描線的核心思維
想像一條垂直線從左往右掃過平面。每次遇到一個「事件」（矩形的左邊、右邊，或線段的端點），就更新當前的「一維狀態」，並計算貢獻。
事件驅動（event-driven）是關鍵：問題的複雜度取決於有多少個事件，而不是整個平面有多大。
矩形聯集面積
n 個矩形，求覆蓋的總面積（重疊部分只算一次）：
把每個矩形拆成兩個事件：
左邊（x=x1）：進入事件，y 範圍 [y1, y2] 加入活躍集合
右邊（x=x2）：離開事件，移除 [y1, y2]
按 x 座標排序所有事件
掃描線移動時：
在每個 x 位置，計算活躍 y 區間的總覆蓋長度
面積貢獻 = 覆蓋長度 × 與下一個事件的 x 距離
y 區間覆蓋長度用線段樹維護（區間加、查詢有效覆蓋長度）
總時間：O(n log n)
線段交點偵測（Shamos-Hoey）
判斷 n 條水平/垂直線段中是否有交點：
事件：
水平線段 [x1, x2, y]：x1 時插入 y，x2 時刪除 y
垂直線段 [x, y1, y2]：在 x 時查詢 [y1, y2] 範圍內有沒有水平線段
用 TreeSet 維護活躍水平線段（按 y 排序）
垂直線段事件時，用 headSet/tailSet 做範圍查詢
O(n log n + k)，k = 交點數
最近點對
n 個點，找距離最近的兩個：
1. 按 x 排序
2. 維護一個活躍視窗：窗口內的點到掃描線 x 距離 ≤ 當前最近距離 d
3. 加入新點 p 時：
a. 移除 x 距離 > d 的點（維護窗口）
b. 在窗口內找 y 差距 < d 的點，更新 d
c. 把 p 加入窗口
關鍵：幾何論證說明，在 2d × d 的矩形內最多有 8 個點
→ 每次內層搜尋是 O(1)，總 O(n log n)
掃描線的通用模板
// 定義事件：x 座標、類型（-1 結束/0 查詢/1 開始）
List<Event> events = generateEvents(...);
// 排序：同 x 先處理結束事件，再處理查詢，再處理開始
Collections.sort(events);
ActiveSet active = new TreeSet<>(); // 或線段樹
for (Event e : events) {
if (e.type == 1) active.add(e.data);
else if (e.type == -1) active.remove(e.data);
else process(active.rangeQuery(e.queryRange));
}掃描線的精髓是「固定一個維度當時間軸」——把靜態的二維幾何問題轉成動態的一維維護問題。