F - ダブルス
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 800 点
問題文
くじら君とかつお君はダブルスのペアを組み、テニスの大会に出場することにしました。 2人は次の試合で敵のボールをすべて打ち返し、完封勝ちしたいと考えています。 そのために自分たちがどれだけ本気を出せばいいか計算することにしました。
簡単のため、テニスコートを1本の数直線で表します(つまり自陣における横方向の移動しか考えず、縦方向の差は考えないものとします)。 2人は最初、時刻 0 において原点に立っています。 2人は任意の時刻において、速さ V 以下で移動するか静止することができます。 2人の速さの上限 V は共通ですが、それ以外は独立に移動することができます。すれちがうことも、同じ時刻に同じ位置にいることもできます。
今から N 個のボールが飛んできます。 i 番目のボールは時刻 T_i に位置 X_i に飛んできます。 i 番目のボールを打ち返すには時刻 T_i に少なくとも1人が位置 X_i にいなければなりません。 2人がすべてのボールを打ち返すための速さの上限 V の最小値を求めてください。
制約
- 入力はすべて整数である。
- 1 ≦ N ≦ 10^5
- 1 ≦ T_i ≦ 10^9
- i < j のとき T_i < T_j
- −10^6 ≦ X_i ≦ 10^6
部分点
- 600 点分のテストケースでは 1 ≦ N ≦ 2000 が満たされる。
入力
入力は以下の形式で標準入力から与えられる。
N T_1 X_1 T_2 X_2 : T_N X_N
出力
2人がすべてのボールを打ち返すための速さの上限 V の最小値を出力せよ。絶対誤差または相対誤差が 10^{−6} 以下ならば正解となる。
入力例 1
4 1 2 2 4 5 0 6 4
出力例 1
2.0000000000
入力例 2
5 1 3 2 -6 3 9 4 -12 5 15
出力例 2
3.0000000000
入力例 3
6 1 0 2 0 3 0 4 0 5 0 6 0
出力例 3
0.0000000000
入力例 4
3 1 0 3 5 5 0
出力例 4
1.6666666667
入力例 5
4 1 5 2 -10 4 0 5 -20
出力例 5
5.0000000000