Module: 三元搜索


Problem

3 /9


自行车比赛

Problem

参加公路赛的车手,在某个时间点,称为初始,在距离起点x1,x2, .. ., xn 米(n - 骑车人的总数)。每个骑车人以他自己的恒定速度 v1, v2, ..., vn 米每秒移动。所有骑自行车的人都朝同一个方向移动。
 
一名赛事记者想要确定比赛中领先的自行车手和最后一名自行车手之间的距离最短的时间点,以便从直升机上同时拍摄自行车比赛的所有参与者。
 
要求编写一个程序,给定骑车人的数量n,给定骑车人的初始位置x1, x2, ..., xn > 和它们的速度 v1, v2, ..., vn, 将计算时间 t,此时距离 l领先和落后的骑车人是最小的。
 
输入
输入文件的第一行包含整数 n –骑自行车的人数。
 
接下来的 n 行每行包含两个整数:xi –初始时间从起点到第 i 个自行车手的距离 (0 ≤ xi ≤  107 ) 和 vi –它的速度是 (0 ≤ vi 10 7 ).
 
输出
需要输出两个实数到输出文件:t –从初始时刻到领队和拖车之间以米为单位的距离最小时经过的时间(以秒为单位), l –所需的距离。
 
数字t和l必须有不超过10–6的绝对或相对误差,意思如下。让显示的数字等于 x,在正确答案中它等于 y。如果表达式 |x – 的值是正确的,那么答案将被认为是正确的。是| / 最大值(1,  |y| ) 不超过 10–6.
 
子任务和评分系统
此任务包含四个子任务。为了评估每个子任务,使用了它自己的一组测试。只有当该组的所有测试都通过时,子任务才会获得分数。
  <正文>
  个人奥林匹克运动会,全俄学生奥林匹克运动会,决赛阶段,2011 年,F 题
输入 输出
3
0 40
30 10
40 30
1 30
5
90 100
100 70
100 70
110 60
120 35
0.5 5.000000000000