BZOJ 3190 [JLOI2013] 賽車：半平面交判定領跑車輛

問題建模

N 輛賽車在無限長直線上，第 i 輛車初始位置 k_i，速度 v_i（恆定）。若某車曾處於領跑位置（無其他車在其前方），則獲獎。求所有獲獎車輛編號（從小到大）。

車輛位置隨時間 t 變化：x_i(t) = k_i + v_i * t。領跑條件：存在 t ≥ 0 使得 x_i(t) ≥ x_j(t) 對所有 j 成立。即直線 y = v_i * x + k_i 在 x ≥ 0 區間曾是上包絡線的一部分。

幾何轉化：半平面交

考慮 (v, k) 平面。車 i 領跑 ⇔ 存在 t ≥ 0 使 k_i + v_i t ≥ k_j + v_j t (∀j)。整理得：(v_i - v_j) t ≥ k_j - k_i。

• 若 v_i = v_j：需 k_i ≥ k_j。同速度下，只保留初始位置最大者（若並列則都保留）。
• 若 v_i > v_j：t ≥ (k_j - k_i) / (v_i - v_j)。對於所有 v_j < v_i 的 j，需 t ≥ max{...}。
• 若 v_i < v_j：t ≤ (k_j - k_i) / (v_i - v_j)。對所有 v_j > v_i 的 j，需 t ≤ min{...}。

綜合：車 i 獲獎 ⇔ max_{v_j < v_i} (k_j - k_i)/(v_i - v_j) ≤ min_{v_j > v_i} (k_j - k_i)/(v_i - v_j) 且該區間與 [0, +∞) 有交集。這等價於點 (v_i, k_i) 在所有直線 y = v_j x + k_j (x ≥ 0) 形成的上凸包上。

算法流程

1. 按速度 v 升序排序，v 相同則按 k 降序（保留 k 最大者，並列同 v 同 k 全保留）。
2. 維護上凸包（單調棧）。向量叉積判斷凸性：cross(a, b, c) = (b.v - a.v)*(c.k - a.k) - (b.k - a.k)*(c.v - a.v)。
3. 入棧前，移除棧頂使新點不破壞上凸包凸性（cross ≤ 0）。
4. 入棧後，移除棧頂使其不被新點「遮蓋」（即棧頂點在新點對應直線下方，cross < -eps）。
5. 最終棧中車輛即為獲獎車輛。

特殊情況處理

• 相同 (v, k) 的車輛：全保留，編號全輸出。
• 精度：使用 double 並設 eps = 1e-8 比較。
• 複雜度：排序 O(N log N)，單調棧 O(N)，總 O(N log N)，N ≤ 10,000 極快。

代碼關鍵點

提供的 C++ 代碼實現上述邏輯，結構體 car 含 p, v, id。cmp 排序，cross 計算叉積。主循環雙重 while 維護凸包。最後收集棧中 id 排序輸出。注意 vector v[maxn] 未使用，可能為殘留代碼。

總結

本題將動態領跑問題轉化為靜態幾何問題，利用半平面交（上凸包）思想，通過單調棧線性求解，是計算幾何在算法競賽中經典應用。