追逐 T3
题目描述
这次,LYK以一个上帝视角在看豹子赛跑。
在一条无线长的跑道上,有n只豹子站在原点。第i只豹子将在第ti个时刻开始奔跑,它的速度是vi/时刻。
因此在不同的时刻,这n只豹子可能在不同的位置,并且它们两两之间的距离也将发生变化。
LYK觉得眼观八方太累了,因此它想找这么一个时刻,使得最远的两只豹子的距离尽可能近,当然这不能是第0时刻或者第0.01时刻。它想知道的是最迟出发的豹子出发的那一刻开始,离得最远的两只豹子在距离最小的时候这个距离是多少。
当然这个时刻不仅仅可能发生在整数时刻,也就是说可能在1.2345时刻这个距离最小。
输入格式(chase.in)
第一行一个数n。
接下来n行,每行两个数分别是ti和vi。
输出格式(chase.out)
输出一个数表示答案,你只需保留小数点后两位有效数字就可以了。
输入样例
3
1 4
2 5
3 7
输出样例
0.33
样例解释
在第5+2/3这个时刻,第一只豹子在18+2/3这个位置,第二只豹子在18+1/3这个位置,第三只豹子在18+2/3这个位置,最远的两只豹子相距1/3的距离,因此答案是0.33。
数据范围
对于20%的数据n=2。
对于20%的数据n=3
对于60%的数据n<=100。
对于80%的数据n<=1000。
对于100%的数据n<=100000,1<=vi,ti<=100000。
信息
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 2
- 已通过
- 1
- 通过率
- 50%
- 上传者