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

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:

• 2 ≤ N ≤ 200 000.
• All x and z are in the range −10⁹ ≤ x, z ≤ 10⁹.
• All x in the input are distinct.

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