#55025: 解題思路
🚗 ZeroJudge a426 - 車車競賽 解題報告
📋 題目理解
有 n 輛車在二維平面上，每輛車有：
- 一條線段軌跡 (x1, y1) 到 (x2, y2)
- 一個移動方向（0=左、1=上、2=右、3=下）
- 一個出發順序編號
核心問題：找出最小的出發順序編號，使得該車輛會與其他車輛相撞。
🔍 問題分析
碰撞條件
兩輛車 A 和 B 會相撞，當且僅當：
- 它們的軌跡線段有交集（或重疊部分）
- A 往 B 的方向移動，B 往 A 的方向移動（相向而行）
- 出發順序較後的車輛會先到達交集點
關鍵觀察
左右方向的碰撞：對於水平方向移動的車輛，碰撞取決於「x 軸上的偏序關係」。我們需要知道哪些線段在 x 方向上「誰在誰的左邊」。
上下方向的碰撞：對於垂直方向移動的車輛，碰撞取決於「y 軸上的偏序關係」。我們需要知道哪些線段在 y 方向上「誰在誰的下面」。
🎯 解法核心思想
1. 建立偏序關係 (DAG)
目標：為所有線段建立 x 方向和 y 方向的偏序關係
方法：掃描線 + 平面掃描
方法：掃描線 + 平面掃描
- 使用事件點演算法，對每條線段的端點建立事件
- 維護一個活動線段集合（用 set 儲存）
- 當線段進入時，與相鄰線段建立 DAG 邊
- 當線段離開時，連接其左右鄰居
2. 拓撲排序求 Rank
對建立好的 DAG 進行拓撲排序，得到每條線段在 x 方向和 y 方向的 rank 值。
rank_x[i]：線段 i 在 x 方向的相對位置rank_y[i]：線段 i 在 y 方向的相對位置
3. 四個方向分別檢測
針對四個移動方向（左、右、上、下），分別進行碰撞檢測：
方向 0（左）和方向 2（右）：
- 按
rank_x排序線段 - 用線段樹維護「y 區間」內的最大出發順序
- 若往左移動的車，在其 y 範圍內已有出發順序更大的車往右移動 → 碰撞！
方向 1（上）和方向 3（下）：
- 按
rank_y排序線段 - 用線段樹維護「x 區間」內的最大出發順序
- 若往上移動的車，在其 x 範圍內已有出發順序更大的車往下移動 → 碰撞！
🔧 關鍵技術細節
1. 座標壓縮
由於座標範圍可能很大，需要進行座標壓縮：
- 收集所有 y 座標，排序去重，映射到 [0, M-1]
- 收集所有 x 座標，排序去重，映射到 [0, MX-1]
2. 線段樹區間更新與查詢
使用 Iterative Segment Tree 實現：
update(l, r, value)：將區間 [l, r) 的最大值更新為 max(原值, value)query(l, r)：查詢區間 [l, r) 的最大值- 使用 lazy propagation 優化
3. 幾何判斷：線段位置關係
在
build_dag 中的比較函數使用叉積判斷：
- 給定兩條線段 A 和 B，在某個 y 值處判斷誰在左邊
- 使用向量叉積判斷點相對於直線的位置
- 時間複雜度 O(1)
⚙️ 演算法流程
Step 1：讀入數據，標準化線段（確保 p1.y ≤ p2.y）
Step 2：建立 x 方向的 DAG，得到
rank_xStep 3：交換 x, y 座標，建立 y 方向的 DAG，得到
rank_yStep 4：座標壓縮（Y 座標和 X 座標）
Step 5：檢測四個方向的碰撞
- 方向 0（左）：按 rank_x 從小到大處理
- 方向 2（右）：按 rank_x 從大到小處理
- 方向 3（下）：按 rank_y 從小到大處理
- 方向 1（上）：按 rank_y 從大到小處理
Step 6：輸出找到的最小碰撞車輛編號
📊 複雜度分析
時間複雜度：O(n² log n)
- 建立 DAG：O(n² log n) — 掃描線 + set 操作
- 拓撲排序：O(n + E)，其中 E = O(n²)
- 四次掃描 × 線段樹操作：O(n log n)
空間複雜度：O(n²)
- DAG 邊數：O(n²)
- 線段樹：O(n)
💡 重點技巧總結
1. 計算幾何 + 圖論結合：透過幾何關係建立 DAG，再用拓撲排序得到偏序
2. 座標旋轉技巧：交換 x, y 座標，可以用同一套程式碼處理兩個方向
3. 線段樹優化：使用區間最大值查詢，避免暴力比對所有車輛對
4. FastIO 優化：由於數據量大，使用快速讀入加速
🎓 學習要點
- 掃描線演算法在計算幾何中的應用
- 如何用 DAG 表達偏序關係
- 線段樹的區間更新與懶惰標記
- 叉積在判斷線段位置關係中的應用
- 多維度問題的分解處理技巧