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