깨진 타일
시간 제한0.5초메모리 제한512 MB
직사각형을 단조 직각 곡선으로 두 조각 낸 뒤, 두 조각을 직사각형으로 나눌 때 가능한 최소 변 길이의 최댓값을 구합니다.
문제
직사각형 타일이 바닥에 떨어져 두 조각으로 깨졌다. 다행히 타일은 아래 왼쪽 그림처럼 타일의 변에 대해 단조인 직교 곡선을 따라 깨졌다. 직교 곡선은 선분들로 이루어진다. 직교 곡선 R이 직선 또는 선분 L에 대해 단조라는 것은, L에 수직인 모든 직선이 R과 최대 한 번 만난다는 뜻이다.
타일은 직사각형이어야 하므로, 조각을 커터로 더 잘라 직사각형 타일로 만들기로 했다. 조각의 변을 지나는 직선을 따라 자르는 것을 직사각형 절단이라고 부른다. 직사각형 절단을 하면 두 조각은 직사각형들로 나뉜다. 가능한 모든 직사각형 절단 중에서, 결과로 나온 직사각형들의 변 길이 최솟값이 가장 커지는 절단을 찾고 싶다.
예를 들어 위 왼쪽 그림은 가로 17, 세로 11인 축에 평행한 직사각형을 보여준다. 이 직사각형은 점 (4,0), (4,4), (11,4), (11,8), (13,8), (13,11)을 순서대로 잇는 선분들로 이루어진 단조 직교 곡선을 따라 두 조각으로 깨졌다. 직사각형 절단에서는 (4,4), (11,4), (11,8), (13,8) 중 한 꼭짓점에서 시작해 수평선, 수직선, 또는 둘 다를 따라 각 조각을 자를 수 있다. 오른쪽 그림은 한 직사각형 절단을 보여준다. 왼쪽 조각은 (4,4)와 (11,8)에서 수평선을 고르고, 오른쪽 조각은 (13,8)에서 수평선을, (11,4)에서 수직선을 고른다. 이 절단으로 두 조각은 직사각형 R1, R2, ..., R6으로 나뉜다. R1과 R6의 변 길이 최솟값이 3으로 여섯 직사각형 중 가장 작으므로, 이 절단의 변 길이 최솟값은 3이다. 이 절단은 깨진 조각들에 대한 모든 직사각형 절단 중에서 변 길이 최솟값을 가장 크게 만든다.
입력
첫 줄에 정수 a와 b (1 ≤ a ≤ 100,000, 1 ≤ b ≤ 100,000)가 주어진다. 이는 왼쪽 아래 꼭짓점이 (0,0)인 축에 평행한 직사각형의 오른쪽 위 꼭짓점의 x 좌표와 y 좌표이다. a = b = 1인 입력은 없다. 다음 줄에는 직사각형을 두 조각으로 나누는 단조 직교 곡선의 점 개수 n (2 ≤ n ≤ 100,000)이 주어진다. 이어지는 n개의 줄에는 각각 정수 c와 d (0 ≤ c ≤ a, 0 ≤ d ≤ b)가 주어지며, 곡선 위에서 i번째 점의 x 좌표와 y 좌표이다. 모든 점은 서로 다르다.
출력
한 줄만 출력한다. 그 줄에는 가능한 모든 직사각형 절단 중에서 변 길이 최솟값의 최댓값을 적는다.