You have located a major supply line that the enemy has been using. With satellite imaging, you’ve been able to determine the current location and velocity of every vehicle along the supply line, which is for all practical purposes an infinitely long straight line. Furthermore, you know that each vehicle moves at constant velocity, and that they can pass by each other without incident along this supply line. What you need to do now is deploy an air drone with special sensors that can give you readings of the contents of the vehicles. The sensor is capable of reading everything in its range instantaneously, but power limitations allow it to do so only once. In order to minimize the required range, you want to deploy it when the vehicles are as close to each other as possible. Given knowledge of the current location and velocity of all the vehicles, what is the closest that the vehicles will get to each other?


There will be a single test case in the input. This test case will begin with a line with a single integer $n$ ($1 \le n \le 100\, 000$) representing the number of vehicles. Each of the next $n$ lines will have two integers, $x$ and $v$ ($-100\, 000 \le x,v \le 100\, 000$), indicating the position ($x$, in meters) and velocity ($v$, in meters/hour) of that vehicle. The sign of velocity indicates direction.


Output a single number equal to the minimum distance that will cover all of the vehicles at some time, in meters. Your result should have an absolute or relative error of less than $10^{-3}$.

Sample Input 1 Sample Output 1
-100 1
100 -1
Sample Input 2 Sample Output 2
-100 1
100 -1
101 -1
Sample Input 3 Sample Output 3
-100 -1
0 0
100 1
CPU Time limit 2 seconds
Memory limit 1024 MB
Difficulty 3.6medium
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in