Hide

Problem F
Lipschitz Constant

Today you are doing your calculus homework, and you are tasked with finding a Lipschitz constant for a function f(x), which is defined for N integer numbers x and produces real values. Formally, the Lipschitz constant for a function f is the smallest real number L such that for any x and y with f(x) and f(y) defined we have:

|f(x)f(y)|L|xy|.

Input

The first line contains N – the number of points for which f is defined. The next N lines each contain an integer x and a real number z, which mean that f(x)=z. Input satisfies the following constraints:

  • 2N200000.

  • All x and z are in the range 109x,z109.

  • All x in the input are distinct.

Output

Print one number – the Lipschitz constant. The result will be considered correct if it is within an absolute error of 104 from the jury’s answer.

Sample Input 1 Sample Output 1
3
1 1
2 2
3 4
2
Sample Input 2 Sample Output 2
2
1 4
2 2
2
Sample Input 3 Sample Output 3
4
-10 6.342
-7 3
46 18.1
2 -34
4.111111111
Hide

Please log in to submit a solution to this problem

Log in