The cyclists participating in the road race, at some point in time, which is called the initial, ended up at points remote from the starting point by x1, x2, .. ., xn meters (n – total number of cyclists). Each cyclist moves with his own constant speed v1, v2, ..., vn meters per second. All cyclists move in the same direction.
A race reporter wants to determine the point in time at which the distance between the leading cyclist in the race and the last cyclist will be minimal in order to photograph all the participants of the cycling race from a helicopter at once.
It is required to write a program that, given the number of cyclists n, the given initial positions of the cyclists x1, x2, ..., xn > and their velocities v1, v2, ..., vn, will calculate the time t at which the distance l between the leading and trailing cyclist is minimal.
Input
The first line of the input file contains the integer n – number of cyclists.
The next n lines contain two integers each: xi – distance from the start to the i-th cyclist at the initial time (0 ≤ xi ≤ 107 ) and vi – its speed is (0 ≤ vi ≤ 10 7 ).
Output
It is necessary to output two real numbers to the output file: t – time in seconds elapsed from the initial moment of time until the moment when the distance in meters between the leader and the trailer is minimal, l – desired distance.
The numbers t and l must have an absolute or relative error of no more than 10–6, which means the following. Let the displayed number be equal to x, and in the correct answer it is equal to y. The answer will be considered correct if the value of the expression |x – y| / max(1, |y| ) does not exceed 10–6.
Subtasks and scoring system
This task contains four subtasks. To evaluate each subtask, its own group of tests is used. Points for a subtask are awarded only if all tests from this group are passed.
| Input |
Output |
|
3
0 40
30 10
40 30
|
1 30 |
|
5
90 100
100 70
100 70
110 60
120 35
|
0.5 5.000000000000 |
Individual Olympiads, All-Russian Olympiad for schoolchildren, Final stage, 2011, Problem F