D - 数直線 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

問題文

数直線上に N 個の点があり、i 番目の点の座標は x_i です。また、N 個の整数 w_i が与えられます。

次の条件を満たす点 p の座標を求めてください。条件を満たす点が複数ある場合は、最も座標が小さいものを求めてください。

条件: 「1≤i≤N を満たす整数 i に対する (p から点 i までの距離) × w_i の最大値が最小になる。」

制約

  • 1 ≤ N ≤ 10^5
  • |x_i| ≤ 10^7
  • x_i < x_{i+1} (1 ≤ i ≤ N-1)
  • 1 ≤ w_i ≤ 10^7
  • 入力で与えられる値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
x_1 w_1
:
x_N w_N

出力

条件を満たす点 p の座標の最小値を出力せよ。絶対誤差または相対誤差が 10^{−9} 以下ならば正解となる。

入力例 1

6
-9 1
-6 1
-4 1
1 1
9 1
10 1

出力例 1

0.500000000000

点 p の座標が 0.5 のとき、各点 i (1≤i≤N) に対する (p から点 i までの距離) × w_i の値はそれぞれ 9.5, 6.5, 4.5, 0.5, 8.5, 9.5 となり、 これらの最大値は 9.5 です。 この値をこれより小さくすることはできないので、答えは 0.5 です。

入力例 2

20
-8965725 4915988
-8830129 1578539
-8356752 3503810
-7479989 5100308
-6995994 3722838
-6861764 3493854
-6486775 1657800
-4577872 7994227
-3685008 7178154
-3169623 9319261
-2694681 7493276
-1967934 3837689
-1634671 544297
-1232484 6010778
2733239 4318924
4797695 2789412
5713704 4416095
6609027 2426329
6997023 2155233
7812383 9912027

出力例 2

2249873.278320866637