配点 : 800 点
問題文
久次良君和胜雄君组成双打组合,并决定参加网球锦标赛。 两人希望在下一场比赛中将对手的球全部归还,赢得一场绝杀。 为了实现这一目标,我们决定计算一下我们应该有多认真。
为了简单起见,我们将网球场表示为单条数轴(换句话说,我们只会考虑己方的水平移动,而不会考虑垂直差异)。 起初,他们两个人当时就开始了。 我们正处于 0 的起点。 任意给定时间两个人的速度 V 你可以在下面移动或静止。 两人最高速度限制 V 很常见,但其他的可以独立移动。你们可以互相擦肩而过,也可以同时出现在同一个位置。
从现在开始 N 球会飞向你。 i 第一个球是时间 位于 T_i 它将飞往 X_i 。 i 回击球的时间 至少 1 人位于 T_i 必须位于 X_i 中。 两人将所有球击回的速度上限 找到 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
出力
两人击回所有球的速度上限 打印 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