흥미로운 커플

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

요약

맨해튼 거리로 주어진 N개의 점에서 두 점 사이 거리 d(i, j)가 p(i, j) 이하인 쌍을 찾고, 그 중 p(i, j)의 최솟값을 구합니다.

난이도: 보통10점 중 7점
유형: 기하, 정렬, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

당신은 넓은 방에서 $N$ 명의 손님(번호는 $1$ 번부터 $N$ 번까지)을 초대해 파티를 연다. 파티 방은 2차원 직교 좌표 평면으로 볼 수 있으며, 손님 $i$ 는 $(X_i, Y_i)$ 에 서 있다. 각 손님은 방 안에서 수평 방향 또는 수직 방향으로만 움직일 수 있다.

두 손님 $i$ 와 $j$ 사이의 거리 $d(i, j)$ 는 두 사람이 서로에게 가기 위해 수평과 수직 방향으로 이동해야 하는 거리의 합이다. 즉 $d(i, j) = |X_i - X_j| + |Y_i - Y_j|$ 이다.

두 손님 $i$ 와 $j$ 의 프라이버시 값 $p(i, j)$ 는 $k \ne i$ 이고 $k \ne j$ 인 모든 $k$ 에 대한 $\min(d(i, k), d(j, k))$ 의 최솟값이다. 다시 말해, 두 사람 각각이 가장 가까운 다른 손님과 얼마나 떨어져 있는지로 정해진다.

두 손님 $i$ 와 $j$ 가 $p(i, j) \ge d(i, j)$ 를 만족하면 둘은 흥미로운 커플이다.

흥미로운 커플들 중 $p(i, j)$ 의 최솟값을 구하라.

입력

첫 줄에 정수 $N$ ( $3 \le N \le 100000$ )이 주어진다. 다음 $N$ 개 줄에는 각각 정수 $X_i$ 와 $Y_i$ ( $0 \le X_i, Y_i \le 10^9$ )가 주어진다. 같은 위치에 서 있는 손님은 없다. 즉, $1 \le i < j \le N$ 인 모든 $i, j$ 에 대해 $(X_i, Y_i) \ne (X_j, Y_j)$ 이다.

주어진 제약 조건에서 흥미로운 커플은 항상 존재한다.

출력

흥미로운 커플들 중 $p(i, j)$ 의 최솟값을 정수 하나로 출력한다.

예제4

예제 1
입력
```
4
3 2
6 4
3 4
4 7
```
예상 출력
```
3
```
예제 2
입력
```
3
4 6
8 6
6 4
```
예상 출력
```
4
```
예제 3
입력
```
5
1 5
2 5
11 5
12 5
20 5
```
예상 출력
```
8
```
예제 4
입력
```
5
4 4
4 3
4 5
3 4
5 4
```
예상 출력
```
1
```