33098번 - Interesting Couple 다국어

문제

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.

제한

힌트