This page is still under construction.

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

Bicycle Race

Interview

Time limit2sMemory limit512 MB

Summary
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 x1,x2,…,xnx_1, x_2, \ldots, x_n meters from the start (nn is the number of cyclists). Each cyclist moves at a constant speed of v1,v2,…,vnv_1, v_2, \ldots, v_n 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 nn, their initial positions x1,x2,…,xnx_1, x_2, \ldots, x_n, and their speeds v1,v2,…,vnv_1, v_2, \ldots, v_n, write a program that computes the moment tt when the distance ll between the leading and trailing cyclists is minimal.

Input

The first line contains the integer nn, the number of cyclists.

The next nn lines each contain two integers: xix_i, the distance from the start to cyclist ii at the initial moment (0≤xi≤1070 \le x_i \le 10^7), and viv_i, the speed of that cyclist (0≤vi≤1070 \le v_i \le 10^7).

Output

Output two real numbers: tt, the time in seconds from the initial moment until the distance in meters between the leader and the trailing cyclist is minimal, and ll, that distance.

The numbers tt and ll must have an absolute or relative error of at most 10−610^{-6}. Let the output number be xx and the correct answer be yy. The answer is accepted if ∣x−y∣/max⁡{1,∣y∣}|x - y| / \max\{1, |y|\} does not exceed 10−610^{-6}.

Constraints

2≤n≤1052 \le n \le 10^5.

Examples2

  1. Example 1

    Input
    3
    0 40
    30 10
    40 30
    
    Expected output
    1 30
    
  2. Example 2

    Input
    5
    90 100
    100 70
    100 70
    110 60
    120 35
    
    Expected output
    0.5 5.000000000000