크리켓 경기장

시간 제한2초메모리 제한128 MB

요약

가로 W, 세로 H인 직사각형 공원에 최대 100그루의 나무 좌표가 주어질 때, 나무를 내부에 포함하지 않는 가장 큰 축 정렬 정사각형의 한 변 길이를 구한다.

난이도: 보통10점 중 6점
유형: 기하, 완전 탐색, 정렬
정답자: 아직 제출이 없습니다

문제

탐욕스러운 왕이 건축가에게 왕궁 공원 안에 정사각형 크리켓 경기장을 지으라고 명령했다. 왕은 나무를 단 한 그루도 베거나 새로 심는 것을 허락하지 않으면서도, 가능한 한 가장 큰 경기장을 요구한다. 건축가가 그런 경기장을 찾도록 도와주자.

공원은 평평한 지면 위의 직사각형이며 그 변은 좌표축과 나란하고, 크리켓 경기장은 좌표축과 나란한 정사각형이다. 건축가의 좌표계에서 공원의 남서쪽 모서리는 $(0, 0)$ , 북동쪽 모서리는 $(W, H)$ 이며, $W$ 와 $H$ 는 각각 공원의 너비와 높이(피트)이다.

나무의 지름은 무시하므로 각 나무는 하나의 점이다. 어떤 나무도 경기장 내부에 들어가서는 안 되지만, 경기장의 변 위에 놓이는 것은 허용된다. 경기장은 공원의 경계에 닿을 수는 있으나 공원 밖으로 나가서는 안 된다.

크리켓 경기장의 가능한 최대 한 변의 길이를 구하여라.

입력

첫째 줄에 세 정수 $N$ , $W$ , $H$ 가 주어진다 ( $0 \le N \le 100$ , $1 \le W, H \le 10000$ ). 각각 나무의 개수와 공원의 너비, 높이(피트)이다.

다음 $N$ 개의 줄에는 각각 두 정수 $X_i$ 와 $Y_i$ 가 주어진다 ( $0 \le X_i \le W$ , $0 \le Y_i \le H$ ). $i$ 번째 나무의 좌표이며, 모든 나무의 좌표는 서로 다르다.

출력

공원 안에 완전히 들어가면서 내부에 어떤 나무도 두지 않는 정사각형 경기장의 최대 한 변의 길이 $L$ 을 정수 하나로 출력한다.

예제3

예제 1
입력
```
7 10 7
3 2
4 2
7 0
7 3
4 5
2 4
1 7
```
예상 출력
```
4
```
예제 2
입력
```
0 1 1
```
예상 출력
```
1
```
예제 3
입력
```
1 4 4
2 2
```
예상 출력
```
2
```