← 返回题目列表

AtCoder · relay2018_d

D. 数直线

中文机器翻译题面 查看原题

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