Description

Crab-style hide-and-seek, as the name suggests, means they can only move horizontally or vertically while playing.

After a lonely round of rock-paper-scissors, they decided that iPig would seek giPi. Since they both know the layout of the Big Fat Pig School very well, giPi will only hide at one of $N$ hidden locations, and iPig will only search among those same $N$ locations.

At the start of the game, they choose one location from these $N$ hidden locations. iPig stays put, and giPi uses $30$ seconds to run away (clearly, giPi will not stay at the starting location). Then iPig will randomly search for giPi until he finds him.

Because iPig is lazy, he always walks along the shortest path. Moreover, he does not choose the starting location arbitrarily—he wants to find a location such that the difference between the distance to the farthest other location and the distance to the nearest other location (excluding the starting location itself) is minimized. iPig now wants to know what this minimum difference is.

Since iPig does not have a computer at hand, he cannot program to solve such a simple problem. He immediately calls you and asks for help. iPig gives you the coordinates of the $N$ hidden locations in the Big Fat Pig School. Please write a program to answer iPig’s question.

Input Format

Line $1$: An integer $N$.

The next $N$ lines: Each line contains two integers $X_i, Y_i$, representing the coordinates of the $i$-th location.

Output Format

One integer, the minimum possible value of the distance difference.

4
0 0
1 0
0 1
1 1

1

Hint

Constraints:

• In $30\%$ of the testdata, $2 \le N \le 10^3$.
• In $100\%$ of the testdata, $2 \le N \le 10^5$, $0 \le X_i, Y_i \le 10^9$.

It is guaranteed that all points are distinct.

Translated by ChatGPT 5