← 返回题目列表

AtCoder · abc419_c

E. 国王峰会

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

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