E - 最大距离

得分: $500$ 分

问题描述

2D 平面上有 $N$ 个点，其中第 $i$ 个点位于 $(x_i, y_i)$ 处。 可能存在多个坐标相同的点。 两个不同点之间的最大曼哈顿距离是多少？

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

约束

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

输入

输入的格式如下，从标准输入中读取：

$N$

$x_1$ $y_1$

$x_2$ $y_2$

$:$

$x_N$ $y_N$

输出

输出答案。

3
1 1
2 4
3 2

4

第一个点和第二个点之间的曼哈顿距离是 $|1-2|+|1-4|=4$，这是最大可能的距离。

2
1 1
1 1

0