分数: 500 点
问题陈述
有 N 2D 平面上的点, 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
输出
打印答案。
示例输入 1
3 1 1 2 4 3 2
示例输出 1
4
第一个点和第二个点之间的曼哈顿距离是 |1-2|+|1-4|=4,这是最大可能的。
示例输入 2
2 1 1 1 1
示例输出 2
0