405298: GYM101875 G Traffic Management

Sancho was making a road trip with his family and got really bored, so he recorded the position and initial speed of every car on the highway. For Sancho, the highway is an infinite straight line, the starting time is 0, the cars are moving points, and no car will pass another car (Sancho is very idealistic).

The cars maintain their initial speed unless they are slowed down by other cars. Car A is slowed down by car B if B started in front of A, but after a while, A reached B. When this happens, both cars move together and A's speed becomes the same as B's.

Sancho knows that there will be only a finite amount of times that a car will be slowed down by another car, and wants to know when the last slowing down will take place. If no car will be slowed down, the answer is 0.

The first line of the input contains a single integer N (1 ≤ N ≤ 10⁵), indicating the number of cars.

N lines follow. The i-th line contains two integers S_i and V_i (0 ≤ S, V ≤ 10⁹), indicating the starting position of the i-th car and its speed. No two cars start in the same position.

Output a single decimal number - the time of the last slow down. Your answer will be considered correct if the absolute or relative error is no greater than 10^- 4.

Namely: let's assume that your answer is a, and the official answer is b. The checker program will consider your answer correct, if .

4
0 10
10 3
20 3
30 2

20.000000