4613 . pC. 倒數影片 (Countdown)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

Description

題目 PDF 檔在這裡

這天是社展即將開始的前幾天，你打算召集所有的建電學術補拍一個即將要發布的倒數影片。

一般來說，我們會在放學時社辦集合，但由於盛夏來臨，社辦的社辦味已經濃到除了因為新冠失去嗅覺的人都難以忍受的程度，因此你決定找個下課選一個最近的地點集合拍倒數，已知要參與的學術都是同屆且教室在同一排，為了確保你的下課有足夠的時間可以打個幾把音遊，因此你想要計算安排在集合所需時間最短的情況下所需要的時間。

在一條橫著的走廊上共有 $n$ 個人，對於第 $i$ 個人，其教室位於座標 $x_i$ ，並可以任何不大於 $v_i$ 的跑速向左或右移動。你的任務是找出可以讓所有人會合的最短時間，會合座標不必為整數。

Input Format

第一行有一個正整數 $n (2 \leq n \leq 5 \cdot 10^4)$ --- 總人數

接下來 $n$ 行，每行兩個整數 $x_i,v_i (1 \leq x_i \leq 10^9, 1 \leq v_i \leq 10^9)$ --- 第 $i$ 個人的初始座標和速度

Output Format

輸出一個實數 $t$，表示可以讓所有人會合的最短時間，絕對或相對誤差不超過 $10^{−6}$ 的任何輸出將被視為正確。具體來說，若你給出的答案是 $a$ 而正確答案是 $b$，只要 $\frac{|a-b|}{max(1, b)} \leq 10^{-6}$，則答案將視為正確。

Sample Input 1

3
7 1
1 2
3 1

Sample Output 1

2.000000000000

Sample Input 2

2
1 1
4 1

Sample Output 2

1.500000000000

Hints

對於第一筆測資：第一個人以最大速率相左前行，而第三及第四個人以最大速率向右前行，則所有人可以在 $2$ 秒內會合到座標 $5$。

Problem Source

TopCoder

roychuang

User's AC Ratio

100.0% (4/4)

Tags

學術上機考 113 學年度

Problem Setter

Created by keaucucal

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 1
2 2~11 $v_i = 1$ 15
3 12~21 $n, x_i, v_i \le 1000$ 30
4 0~39 無其他限制 54

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 65536 1 4
1 1000 262144 262144 65536 1 4
2 1000 262144 262144 65536 2 4
3 1000 262144 262144 65536 2 4
4 1000 262144 262144 65536 2 4
5 1000 262144 262144 65536 2 4
6 1000 262144 262144 65536 2 4
7 1000 262144 262144 65536 2 4
8 1000 262144 262144 65536 2 4
9 1000 262144 262144 65536 2 4
10 1000 262144 262144 65536 2 4
11 1000 262144 262144 65536 2 4
12 1000 262144 262144 65536 3 4
13 1000 262144 262144 65536 3 4
14 1000 262144 262144 65536 3 4
15 1000 262144 262144 65536 3 4
16 1000 262144 262144 65536 3 4
17 1000 262144 262144 65536 3 4
18 1000 262144 262144 65536 3 4
19 1000 262144 262144 65536 3 4
20 1000 262144 262144 65536 3 4
21 1000 262144 262144 65536 3 4
22 1000 262144 262144 65536 4
23 1000 262144 262144 65536 4
24 1000 262144 262144 65536 4
25 1000 262144 262144 65536 4
26 1000 262144 262144 65536 4
27 1000 262144 262144 65536 4
28 1000 262144 262144 65536 4
29 1000 262144 262144 65536 4
30 1000 262144 262144 65536 4
31 1000 262144 262144 65536 4
32 1000 262144 262144 65536 4
33 1000 262144 262144 65536 4
34 1000 262144 262144 65536 4
35 1000 262144 262144 65536 4
36 1000 262144 262144 65536 4
37 1000 262144 262144 65536 4
38 1000 262144 262144 65536 4
39 1000 262144 262144 65536 4
Submit
Back to Top