립시츠 상수
면접 대비시간 제한2초메모리 제한512 MB
N개의 점 (x, f(x))이 주어질 때 x로 정렬한 뒤 인접한 두 점의 기울기 절댓값 중 최댓값을 구합니다.
문제
오늘 미적분학 숙제로, 정수 N개 x에 대해 정의되고 실숫값을 내는 함수 f(x)의 립시츠 상수를 구해야 한다. 함수 f의 립시츠 상수는 f(x)와 f(y)가 정의된 임의의 x, y에 대해 다음을 만족하는 가장 작은 실수 L이다.
|f(x) − f(y)| ≤ L · |x − y|
입력
첫째 줄에 f가 정의된 점의 개수 N이 주어진다. 다음 N개 줄에 정수 x와 실수 z가 주어지며, f(x) = z임을 뜻한다. 입력은 다음 조건을 만족한다.
- 2 ≤ N ≤ 200 000.
- 모든 x와 z는 −10^9 ≤ x, z ≤ 10^9 범위에 있다.
- 입력에 주어지는 x는 모두 서로 다르다.
출력
립시츠 상수를 한 개 출력한다. 결과가 채점 기준 답과 절대오차 10^−4 이내이면 정답으로 인정된다.