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，所以

1. $f_1(t) := \max_{1\leq i\leq n}x_i(t)$ 是 convex function。
2. $f_2(t) := \min_{1\leq i\leq n}x_i(t)$ 是 concave function。
3. $f(t) = f_1(t)-f_2(t)$ 是 convex function。

由 $0 \leq s_i \leq 10^6$ 與 $v_i$ 是整數，可知最小值必定能在 $t \in [0, 10^6]$ 找到。我們可以用三分搜尋法找出 minimizer，並在搜尋區間 $[l, r]$ 滿足 $r-l \leq \delta$ 時結束搜尋。最後，由 $0 \leq v_i \leq 10^6$，可知

$$|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：

https://ideone.com/i93bih