配点 : 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