큰 정사각형 조각
면접 대비시간 제한2초메모리 제한1024 MB
n×m 크기의 케이크를 변에 평행한 k개의 칼집으로 자를 때, 나오는 조각에서 잘라 낼 수 있는 가장 큰 정사각형의 한 변 길이를 구합니다.
문제
페티야는 생일에 가로 n, 세로 m인 직사각형 케이크를 선물로 받았다. 페티야는 직사각형도 좋아하지만 정사각형을 더 좋아해서, 케이크를 같은 크기의 정사각형 조각 여러 개로 자르고 싶어 했다.
그런데 동생 레샤가 먼저 케이크에 손을 대어 변과 평행한 칼집을 몇 번 냈다. 페티야는 속상해했다. 레샤는 형을 위로하려고 잘린 조각 중 하나에서 가능한 가장 큰 정사각형을 잘라내기로 했다. 레샤가 먼저 알아야 할 것은 이 조각들에서 잘라낼 수 있는 정사각형의 최대 한 변 길이다. 레샤를 도와주자.
입력
첫 줄에 세 정수 n, m, k가 주어진다 (1 ≤ n, m ≤ 10^9, 0 ≤ k ≤ 10^5). 다음 k줄에는 자르는 위치가 한 줄에 하나씩 주어진다. 각 줄은 두 수 t와 v로 이루어진다. 케이크의 한 꼭짓점이 (0, 0)이고 맞은편 꼭짓점이 (n, m)이 되도록 좌표계를 잡는다. t = 0이면 직선 x = v를 따라 자른 것이고 (0 ≤ x ≤ n), t = 1이면 직선 y = v를 따라 자른 것이다 (0 ≤ y ≤ m).
출력
케이크를 자른 뒤 생긴 조각들에서 잘라낼 수 있는 정사각형 중 가장 큰 것의 한 변 길이를 한 개의 수로 출력한다.