F - 最大距离2

得分：$500$ 分

问题描述

给定一个二维平面上的 $N$ 个不同的点。第 $i$ 个点 $(1 \leq i \leq N)$ 的坐标为 $(x_i,y_i)$。

我们定义两个点 $i$ 和 $j$ 之间的距离为 $\mathrm{min} (|x_i-x_j|,|y_i-y_j|)$：即$x$坐标差和$y$坐标差的较小值。

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

限制

• $2 \leq N \leq 200000$
• $0 \leq x_i,y_i \leq 10^9$
• $(x_i,y_i)$ $\neq$ $(x_j,y_j)$ $(i \neq 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