P2479 [SDOI2010] Hide and Seek

iPig just finished a boring Pig Language class at the Big Fat Pig School. Being very bright, iPig felt extremely lonely because the class was too easy for him. To fight the loneliness, he decided to play an even lonelier game—hide-and-seek—with his good friend giPi (jī pí). However, they thought regular hide-and-seek was not lonely enough, so they chose to play an extremely lonely crab-style version of hide-and-seek.

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.

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.

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

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