Bicycle Race
InterviewTime limit2sMemory limit512 MB
Each cyclist starts at position x_i with constant speed v_i; find the time t when the spread between the frontmost and rearmost cyclist is smallest, and that spread.
- Level
Medium6 of 10
- Topics
- Sorting, Binary search, Geometry, Math
- Solved
- No attempts yet
Problem
At some moment called the initial moment, the cyclists in a road race are at points meters from the start ( is the number of cyclists). Each cyclist moves at a constant speed of meters per second. All cyclists move in the same direction.
A reporter covering the race wants to find the moment when the distance between the leading cyclist and the trailing cyclist is minimal, so that a helicopter can photograph all the participants at once.
Given the number of cyclists , their initial positions , and their speeds , write a program that computes the moment when the distance between the leading and trailing cyclists is minimal.
Input
The first line contains the integer , the number of cyclists.
The next lines each contain two integers: , the distance from the start to cyclist at the initial moment (), and , the speed of that cyclist ().
Output
Output two real numbers: , the time in seconds from the initial moment until the distance in meters between the leader and the trailing cyclist is minimal, and , that distance.
The numbers and must have an absolute or relative error of at most . Let the output number be and the correct answer be . The answer is accepted if does not exceed .
Constraints
.