AT_abc178_e [ABC178E] Dist Max

题目描述

在二维平面上有 $N$ 个点，第 $i$ 个点的坐标为 $(x_i, y_i)$。有些点可能具有相同的坐标。请问在所有不同的两点之间，曼哈顿距离可能取得的最大值是多少。

其中，两点 $(x_i, y_i)$ 和 $(x_j, y_j)$ 的曼哈顿距离定义为 $|x_i - x_j| + |y_i - y_j|$。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
1 1
2 4
3 2

输出 #1

4

输入输出样例 #2

输入 #2

2
1 1
1 1

输出 #2

0

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq x_i, y_i \leq 10^9$
• 所有输入均为整数

样例解释 1

第 $1$ 个点和第 $2$ 个点的曼哈顿距离为 $|1-2| + |1-4| = 4$，这是所有点对中最大的。

由 ChatGPT 4.1 翻译