[SDOI2010] 捉迷藏

题目背景

iPig 在大肥猪学校刚上完了无聊的猪文课,天资聪慧的 iPig 被这门对他来说无比简单的课弄得非常寂寞,为了消除寂寞感,他决定和他的好朋友 giPi(鸡皮)玩一个更加寂寞的游戏——捉迷藏。但是,他们觉得,玩普通的捉迷藏没什么意思,还是不够寂寞,于是,他们决定玩寂寞无比的螃蟹版捉迷藏。

题目描述

螃蟹版捉迷藏,顾名思义,就是说他们在玩游戏的时候只能沿水平或垂直方向走。 一番寂寞的剪刀石头布后,他们决定 iPig 去捉 giPi。由于他们都很熟悉大肥猪学校的地形了,所以 giPi 只会躲在大肥猪学校内 $N$ 个隐秘地点之一,显然 iPig 也只会在那 $N$ 个地点内找 giPi。 游戏一开始,他们从这 $N$ 个隐秘地点之中选定一个地点,iPig 保持不动,然后 giPi 用 $30$ 秒的时间逃离现场(显然,giPi 不会呆在原地)。然后 iPig 会随机地去找 giPi,直到找到为止。 由于 iPig 很懒,所以他总是走最短的路径,而且,他选择起始点不是随便选的,他想找一个地点,使得该地点到(除了这个地点以外的)最远的地点和最近的地点的距离差最小。iPig现在想知道这个距离差最小是多少。 由于 iPig 现在手上没有电脑,所以不能编程解决这个如此简单的问题,所以他马上打了个电话,要求你帮他解决这个问题。iPig 告诉了你大肥猪学校的 $N$ 个隐秘地点的坐标,请你编程求出 iPig 的问题。

输入输出格式

输入格式


第 $1$ 行:一个整数 $N$; 接下来 $N$ 行:每行两个整数 $X_i,Y_i$,表示第 $i$ 个地点的坐标。

输出格式


一个整数,为距离差的最小值。

输入输出样例

输入样例 #1

4
0 0
1 0
0 1
1 1

输出样例 #1

1

说明

$30\%$ 的数据中,$2\le N\le 10^3$; $100\%$ 的数据中,$2\le N\le 10^5$,$0\le X_i,Y_i\le 10^9$。 数据保证点不重合。