#15 「 去桃李吃饭还是紫荆吃饭 」

统计

whx生活的学校在宿舍区有两个食堂,一个叫桃李,一个叫紫荆。

某动漫社的设定图,桃李是妹妹,紫荆是哥哥

现在有$n$个同学下课归来,有的人刚上完体育课,骑的慢一些,有的人刚在微积分课上睡饱了觉,所以骑的快一些。

具体来说我们把学堂路抽象成一个数轴,第$i$个人开始是一个在$x_i$位置的点,速度为$v_i$。桃李和紫荆都在原点处。

因为只有两条车道,去桃李的同学在左边车道,去紫荆的同学在右边车道,同一个车道的同学之间不能互相超车(可以重合,相当于有$\varepsilon$的距离),不允许变道。

现在同学们想知道,如果请你来安排他们是去桃李吃饭还是紫荆吃饭,所有人到达食堂所花的时间之和最小是多少呢?

输入格式

第一行输入一个整数$n$,表示有$n$个同学。

接下来$n$行,每行两个整数$x_i, v_i$,表示第$i$个同学的位置和速度,保证$x_i$两两不同。

输出格式

一行一个小数表示所有人到达食堂的时间之和最小是多少,答案四舍五入保留四位小数。

样例数据

input1

3
1 2
3 2
5 4

output1

3.2500

input2

3
1 2
3 2
5 11

output2

2.5000

数据规模与约定

$n \leq 5 \times 10^4, x_i \leq 10^6, v_i \leq 10^6$

时间限制:2s

空间限制:512MB

Author: whx