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)| \leq L \cdot |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 \leq N \leq 200\, 000$.

  • All $x$ and $z$ are in the range $-10^9 \leq x,z \leq 10^9$.

  • 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^{-4}$ from the jury’s answer.

Sample Input 1 Sample Output 1
1 1
2 2
3 4
Sample Input 2 Sample Output 2
1 4
2 2
Sample Input 3 Sample Output 3
-10 6.342
-7 3
46 18.1
2 -34
CPU Time limit 6 seconds
Memory limit 1024 MB
Volodymyr Lyubinets
Source 2018 ACM-ICPC North Central North America Regional Contest
License Creative Commons License (cc0)

Please log in to submit a solution to this problem

Log in