박람회

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

요약

평면 위 N개의 점을 두 개의 비어 있지 않은 그룹으로 나눌 때, 같은 그룹 안 두 점 사이 맨해튼 거리의 최댓값을 최소로 만드는 값을 구한다.

난이도: 어려움10점 중 8점
유형: 이분 탐색, 기하, 정렬
정답자: 아직 제출이 없습니다

문제

어느 도시에서 대규모 박람회를 개최한다. 이번 박람회에는 두 가지 테마가 있으며, 도시에 있는 $N$ 개의 전시 시설 각각에서 두 테마 중 정확히 하나를 골라 그 테마에 맞는 전시를 진행한다.

각 시설의 위치는 평면 좌표 $(x, y)$ 로 나타난다. 위치 $(x, y)$ 의 시설에서 위치 $(x', y')$ 의 시설로 이동하는 데에는 $|x - x'| + |y - y'|$ 만큼의 시간이 걸린다(정수 $a$ 에 대해 $|a|$ 는 $a$ 의 절댓값을 뜻한다). 같은 테마 안에서의 통일감을 주고, 한쪽 테마에만 관심 있는 사람이 불편을 느끼지 않도록, 같은 테마로 전시하는 두 시설 사이의 이동 시간이 되도록 짧아지게 테마를 배정하려 한다. 단, 모든 시설에 같은 테마를 배정하는 경우만 아니라면 어떤 방식으로 배정해도 좋다(즉, 두 테마 각각에 적어도 하나의 시설이 배정되어야 한다).

같은 테마로 전시하는 두 시설 사이 이동 시간의 최댓값을 $M$ 이라 하자. $N$ 개 시설의 위치가 주어질 때, $M$ 의 최솟값을 구하여라.

입력

첫째 줄에 시설의 개수 $N$ ( $3 \le N \le 10^5$ )이 주어진다. 이어지는 $i+1$ 번째 줄 ( $1 \le i \le N$ )에는 $i$ 번째 시설의 좌표를 나타내는 두 정수 $x_i$ , $y_i$ ( $|x_i| \le 10^5$ , $|y_i| \le 10^5$ )가 공백으로 구분되어 주어진다. 같은 좌표에 두 개 이상의 시설이 존재하는 경우는 없다.

출력

같은 테마로 전시하는 두 시설 사이 이동 시간의 최댓값 $M$ 의 최솟값을 한 줄에 출력한다.

설명

예를 들어 좌표 $(0, 0)$ , $(1, 0)$ , $(0, 1)$ 의 시설에 한 테마를, $(-1, -2)$ , $(-1, 1)$ 의 시설에 다른 테마를 배정하면 같은 테마로 전시하는 두 시설 사이 이동 시간이 모두 $3$ 이하가 된다. 모든 이동 시간을 $2$ 이하로 만드는 것은 불가능하므로 답은 $3$ 이다.

예제3

예제 1
입력
```
5
0 0
1 0
-1 -2
0 1
-1 1
```
예상 출력
```
3
```
예제 2
입력
```
3
0 0
1 1
2 0
```
예상 출력
```
2
```

예제 3

입력

4
-100000 -100000
100000 100000
-100000 100000
100000 -100000

예상 출력