空港

### 题目描述 现在有 $N$ 个机场，其中第 $i$ 个机场的位置是 $(x_{i},y_{i})$ ， $(x_{i},y_{i})$ 与 $(x_{j},y_{j})$ 之间的距离是 $|x_{i}-x_{j}|+|y_{i}-y_{j}|$ 。要知道，飞机飞一次十分的耗费钱财，为了尽可能减少花费，第 $i$ 个机场的飞机是不会飞去与第 $i$ 个机场距离太近的机场，但是又得保证人们无论在任何一个机场，都能通过直达、转机等手段坐飞机到达他想去的机场（这$N$个机场的任意一个）。 现在机场中心认为，两个机场之间距离在正整数 $X$ 以上的，距离不算太近，可以安排飞机通航。请你求出满足条件的最大$X$。 **数据保证** - $2 \leq N \leq 100,000$ - $0 \leq x_{i},y_{i} \leq 10^{9}$ - 任意两座机场的位置都不相同 ### 输入输出格式 **输入格式：** 第一行一个正整数 $N$ 。接下来 $N$ 行分别是 $(x_{i},y_{i})$ ，表示机场的位置 **输出格式：** 一个正整数 $X$ 。

[problemUrl]: https://atcoder.jp/contests/NYC2015/tasks/nyc2015_8 入力は以下の形式で標準入力から与えられる。 > $ N $ $ x_1 $ $ y_1 $ : $ x_N $ $ y_N $ 答えを一行に出力せよ。 ``` 6 1 7 8 5 6 3 10 3 5 2 6 10 ``` ``` 9 ```

### Constraints すぬけ君は、空港を $ N $ 個持っている。$ i $ 番目の空港の座標は $ (x_i,\ y_i) $ である。すぬけ君は、あまり近い空港の間に飛行機を飛ばしても意味がないので、マンハッタン距離 ($ (x_1,\ y_1) $ と $ (x_2,\ y_2) $ のマンハッタン距離は $ |x_1\ -\ x_2|\ +\ |y_1\ -\ y_2| $) が $ X $ 以上である全ての空港のペアの間に飛行機を飛ばすことにした。どの空港からどの空港へも飛行機だけを使っていけるようになる最大の $ X $ を求めよ。 - - - - - - - $ 2\ \leq\ N\ \leq\ 100000 $ - $ 0\ \leq\ x_i,\ y_i\ \leq\ 10^9 $ - 二つの空港が同じ座標にあることはない。