Lipschitz Constant

Interview

Time limit2sMemory limit512 MB

Summary

Given N points (x, f(x)), the Lipschitz constant is the maximum slope between adjacent points after sorting by x.

Level: Medium5 of 10
Topics: Geometry, Sorting, Math
Solved: No attempts yet

Problem

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 · |x − y|.

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. The input satisfies the following constraints:

2 ≤ N ≤ 200 000.
All x and z are in the range −10^9 ≤ x, z ≤ 10^9.
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 10^−4 from the jury's answer.

Examples3

Example 1
Input
```
3
1 1
2 2
3 4
```
Expected output
```
2
```
Example 2
Input
```
2
1 4
2 2
```
Expected output
```
2
```

Example 3

Input

Expected output

4.111111111