TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

40.0% (12/30)

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

Hints

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

Problem Source

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

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 900 65536
1 900 65536
2 900 65536
3 900 65536
4 900 65536
5 900 65536
6 900 65536
7 900 65536
8 900 65536
9 900 65536
10 900 65536