시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB665100.000%

문제

You are hosting a party with $N$ guests (numbered from $1$ to $N$) in a large room. The party room can be represented as a $2$-dimensional Cartesian space where guest $i$ stands at $(X_i , Y_i)$. Since you have a unique personality, you require each guest to only move horizontally or vertically within this room.

The distance between two guests $i$ and $j$, denoted as $d(i, j)$, is the total distance they need to travel in both horizontal and vertical directions to reach each other, i.e., $d(i, j) = |X_i - Xj | + |Y_i - Yj |$.

The privacy value of two guests $i$ and $j$, denoted as $p(i, j)$, is determined by their distances to the closest other guest. Formally, $p(i, j)$ is the smallest $\min(d(i, k), d(j, k))$ over all $k$ where $k \ne i$ and $k \ne j$.

A pair of guest $i$ and $j$ is an interesting couple if and only if their privacy value is greater or equal to the distance between them. In other words, it is a pair $(i, j)$ such that $p(i, j) ≥ d(i, j)$.

Your task in this problem is to find the minimum value of $p(i, j)$ among all such interesting couples.

입력

The first line consists of an integer $N$ ($3 ≤ N ≤ 100\, 000$).

Each of the next $N$ lines consists of two integers $X_i$ $Y_i$ ($0 ≤ X_i , Y_i ≤ 10^9$). There are no two guests stand at the same location. Formally, $(X_i , Y_i) \ne (X_j , Y_j )$ for $1 ≤ i < j ≤ N$.

Under the given constraints, it can be shown that an interesting couple always exists.

출력

Output an integer representing the minimum value of $p(i, j)$ among all interesting couples.

예제 입력 1

4
3 2
6 4
3 4
4 7

예제 출력 1

3

The only interesting couple is $(1, 3)$, with guest $2$ being the closest guest to this couple. Their privacy value is $\min(d(1, 2), d(3, 2)) = \min(5, 3) = 3$.

예제 입력 2

3
4 6
8 6
6 4

예제 출력 2

4

There are $3$ possible guest pairs, and all of them are interesting couples, each with a privacy value of $4$.

예제 입력 3

5
1 5
2 5
11 5
12 5
20 5

예제 출력 3

8

There are two interesting couples, $(1, 2)$ and $(3, 4)$, with privacy values of $9$ and $8$, respectively.

예제 입력 4

5
4 4
4 3
4 5
3 4
5 4

예제 출력 4

1