This page is still under construction.

Parts of this page are still being built. What you see may change.

Surmising a Sprinter's Speed

Time limit2sMemory limit512 MB

Summary
Given N observations of time and position on a line, find the largest speed the sprinter must have reached at some moment.
Level

Medium6 of 10

Topics
Sorting, Math, Binary search, Greedy
Solved
No attempts yet

Problem

Trick E. Dingo is trying, as usual, to catch his nemesis the Street Sprinter. His past attempts using magnets, traps and explosives have failed miserably, so he's catching his breath to gather observational data and learn more about how fast Street Sprinter is.

Trick E. Dingo and Street Sprinter both inhabit a single straight west-east road with a particularly famous rock on it known affectionately as The Origin. Positions on this straight road are measured numerically according to the distance from The Origin, and using negative numbers for positions west of The Origin and positive numbers for positions east of The Origin.

The observations by Trick E. Dingo each contain two numbers: a time, and the value of Street Sprinter's position on the road at that time. Given this information, what speed must Street Sprinter be capable of?

Input

The first line contains a number 2≤N≤100 0002 \le N \le 100\,000, the number of observations that follow. The next NN lines each contain an integer 0≤T≤1 000 000 0000 \le T \le 1\,000\,000\,000 indicating the time, in seconds, of when a measurement was made, and an integer −1 000 000 000≤X≤1 000 000 000-1\,000\,000\,000 \le X \le 1\,000\,000\,000 indicating the position, in metres, of the Street Sprinter at that time. No two lines will have the same value of TT.

Output

Output a single number XX, such that we can conclude that Street Sprinter's speed was at least XX metres/second at some point in time, and such that XX is as large as possible. If the correct answer is CC, the grader will view XX as correct if ∣X−C∣/C<10−5|X - C|/C < 10^{-5}.

Examples2

  1. Example 1

    Input
    3
    0 100
    20 50
    10 120
    
    Expected output
    7.0
    
  2. Example 2

    Input
    5
    20 -5
    0 -17
    10 31
    5 -3
    30 11
    
    Expected output
    6.8