← 返回题目列表

AtCoder · abc178_e

E. 最大距离

中文机器翻译题面 查看原题

分数: 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