距离最大值 2

题目描述

二维平面上有 $N$ 个互不相同的点。第 $i$ 个点 $(1 \le i \le N)$ 的坐标为 $(x_i,y_i)$。

定义两点 $i$ 和 $j$ 之间的距离为 $\mathrm{min} (|x_i-x_j|,|y_i-y_j|)$，即横坐标差与纵坐标差中的较小值。

求两个不同点之间距离的最大值。

输入格式

输入按以下格式从标准输入给出：

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

输出格式

输出两个不同点之间距离的最大值。

样例

3
0 3
3 1
4 10

4

点 $1$ 和点 $2$、点 $1$ 和点 $3$、点 $2$ 和点 $3$ 之间的距离分别为 $2$、$4$、$1$，所以输出应为 $4$。

4
0 1
0 4
0 10
0 6

0

8
897 729
802 969
765 184
992 887
1 104
521 641
220 909
380 378

801

数据范围

• $2 \le N \le 200000$
• $0 \le x_i,y_i \le 10^9$
• $(x_i,y_i) \neq (x_j,y_j)$ $(i \neq j)$
• 输入中的所有值均为整数。