TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

94.4% (17/18)

Submission's AC Ratio

32.4% (45/139)

Tags

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 1

3
1 1
2 0
3 0

Sample Output 1

0.50

Hints

在第$0.5$秒的時候,三輛車的位置依序是$1.5, 1, 1.5$公尺。此時最前方車子與最後方車子間距為最小值:$0.5$公尺

Problem Source

原TIOJ1284 / [TIOJ] IOI2008 暖身賽 1(prob H)。Problem Setter:Tmt。

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1
1 900 65536 262144 2
2 900 65536 262144 3
3 900 65536 262144 4
4 900 65536 262144 5
5 900 65536 262144 6
6 900 65536 262144 7
7 900 65536 262144 8
8 900 65536 262144 9
9 900 65536 262144 10
10 900 65536 262144 11