二維問題太複雜——固定一個維度，把它變成一連串的一維問題。
掃描線的核心思維
想像一條垂直線從左往右掃過平面。每次遇到一個「事件」（矩形的左邊、右邊，或線段的端點），就更新當前的「一維狀態」，並計算貢獻。
事件驅動（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)（只判斷「有沒有交點」，跟交點數無關）Shamos-Hoey 做的是「有無交點」的布林偵測，只要撞到第一個就能回報，複雜度不帶交點數 k。要「報告全部 k 個交點」是另一件事，得用 Bentley-Ottmann，那個才是 O((n+k) log n)。
最近點對
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));
}排序那行藏了兩個會讓你 debug 到懷疑人生的細節。第一，座標是浮點數時，別直接 Double.compare 比 x——差在 1e-9 內就該當成同一個 x，否則兩個「其實同時發生」的事件會被排出假的先後。第二，同一個 x 上事件的順序不能亂排：一般讓結束（-1）排在開始（1）前面，一個矩形的右邊剛好貼著另一個的左邊時，才不會把它們算成有重疊。這個 tie-break 規則跟你在解什麼題有關，寫之前先想清楚「同一條掃描線上，誰該先動」。
🎬 互動視覺化：掃描線動畫 — 看那條垂直線從左掃到右，每碰一個事件點就更新活躍集合，即時把「當前覆蓋長度 × x 間距」累加成面積，二維問題怎麼被壓成一維維護一目了然。
掃描線的精髓是「固定一個維度當時間軸」——把靜態的二維幾何問題轉成動態的一維維護問題。
接下來往哪走
- 莫隊演算法：把亂序查詢變成有序移動 — 下一篇：同樣是「重排處理順序省計算」的調度思想
- Computational Geometry 計算幾何基礎 — 線段相交、叉積判斷這些掃描線事件處理的幾何基礎
- Segment Tree 線段樹 — 活躍集合需要區間統計時（矩形面積並），TreeSet 就要換成它