Dist Max 2

题目描述

平面上有 $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$ 坐标之差中较小的那个。 求任意两个不同点之间的最大距离。

输入格式

输入从标准输入按以下格式给出： $N$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_N$ $y_N$

输出格式

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

3
0 3
3 1
4 10

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 \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)$ 输入中的所有数值均为整数。点 $1$ 和点 $2$、点 $1$ 和点 $3$、点 $2$ 和点 $3$ 之间的距离分别为 $2$、$4$ 和 $1$，因此输出应为 $4$。

标签: AtCoder|abc215F

来源

AtCoder|abc215F