AT_abc215_f [ABC215F] Dist Max 2

题目描述

在二维平面上给定 $N$ 个互不相同的点。第 $i$ 个点的坐标为 $(x_i, y_i)$。

对于两个点 $i, j\ (1 \leq i, j \leq N)$，定义它们之间的距离为 $\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$

输出格式

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

输入输出样例 #1

输入 #1

3
0 3
3 1
4 10

输出 #1

4

输入输出样例 #2

输入 #2

4
0 1
0 4
0 10
0 6

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

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

点 $1$ 和点 $2$ 的距离为 $2$，点 $1$ 和点 $3$ 的距离为 $4$，点 $2$ 和点 $3$ 的距离为 $1$。因此应输出 $4$。

由 ChatGPT 4.1 翻译