TIOJ 1284 賽車問題
Description
現在有 $n$ 輛往右邊跑的賽車，每一輛都有其固定的車速以及起始位置。你是一位專業的攝影師，而你相信你的專業，順從你的渴望，你希望能夠抓準時機，一次把所有賽車通通照下來。
如果要把所有賽車通通照下來，那麼你的底片要夠長才行。
為了節省成本，你想要知道在所有時刻中，什麼時候最領先的車子跟最落後的車子的距離會最短。
手癢的你趕快來寫個程式求出最短距離吧！
Input Format
輸入的第一列有一個正整數 $n$ ($2\leq n\leq 100,000$)。
接下來有 $n$ 列，每列有兩個整數 $v_i, s_i$ 依序代表第 $i$ 輛賽車的車速(單位：公尺/秒)以及起始座標(向右為正，單位：公尺)。
($0\leq v_i, s_i\leq 1,000,000$)
噢對了，所有車子都位於不同的賽道，因此你不必考慮它們追撞的情形，也不用考慮車身的長度。
而且你可以假設所有車子的車速都不相同。
Output Format
請輸出所有時刻中(時間 $\geq 0$)，最前面的車子與最後面的車子之最小水平間距。
只要四捨五入輸出至小數以下第二位即可。
Sample Input
3
1 1
2 0
3 0
Sample Output
0.50
Solution
這題的 $n$ 實在太大，沒辦法枚舉所有的超車事件來求出答案。注意到答案只要求到小數下第 $2$ 位，可以考慮用近似解。設 $x_i(t)$ 為第 $i$ 台車在 $t$ 秒時的位置，則題目問的就是
\[f(t) := \max_{1 \leq i \leq n} x_i(t) - \min_{1 \leq i \leq n} x_i(t)\]
在 $t \geq 0$ 的最小值。觀察到 $x_i(t) = v_i(t) + s_i$ 既是 convex function 也是 concave function，所以
- $f_1(t) := \max_{1\leq i\leq n}x_i(t)$ 是 convex function。
- $f_2(t) := \min_{1\leq i\leq n}x_i(t)$ 是 concave function。
- $f(t) = f_1(t)-f_2(t)$ 是 convex function。
\[|r-l| \leq \delta \Rightarrow |f(r)-f(l)| \leq 10^6\delta\]
由題目要求可知 $\delta$ 必須滿足 $10^6\delta < 0.005$，故可以取 $\delta = 10^{-10}$。這樣一來，三分搜次數就是 $T := \log_{3/2}10^{16} \approx 90.86$，而整體的時間複雜度是 $O(Tn)$，可在時間限制內解決。
我的 code：
留言
張貼留言