分数: 300 点
问题陈述
有一个网格 10^9 行和 10^9 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
有 N 网格上的人。最初, i第一个人在广场上 (R_i, C_i).
时间开始于 0。每个人有时可以做以下动作 1, 2, 3, 4, \ldots.
- 停留在当前位置,或移动到 8- 相邻的正方形。禁止离开网格。正式地,让平方 (i, j) 为当前方格,并移动到其中一个方格 (i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1) 存在。假设移动不需要时间。
找出当 N 人们在同一个广场。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq R_i, C_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N R_1 C_1 R_2 C_2 \vdots R_N C_N
输出
输出答案。
示例输入 1
3 2 3 5 1 8 1
示例输出 1
3
所有人都将在广场 (5, 4) 时间 3 如果每个人都按如下方式移动。
-
时间 1,第一个人移动到方格 (3, 4),第二个人移动到方格 (6, 2),第三个人移动到方格 (7, 2).
-
时间 2,第一个人移动到方格 (4, 4),第二个人移动到方格 (5, 3),第三个人移动到方格 (6, 3).
-
时间 3,第一个人移动到方格 (5, 4),第二个人移动到方格 (5, 4),第三个人移动到方格 (5, 4).
示例输入 2
5 6 7 6 7 6 7 6 7 6 7
示例输出 2
0
所有人都从同一个广场开始。
示例输入 3
6 91 999999986 53 999999997 32 999999932 14 999999909 49 999999985 28 999999926
示例输出 3
44