← 返回题目列表

AtCoder · abc361_g

G. 去领地

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

分数: 600 点

问题陈述

有 N 石头放置在 2维度平面。的 i-第石头位于坐标处 (X_i, Y_i)。所有石头都位于第一象限(包括轴)的格点处。

计算格点的数量 (x, y) 没有放置石头的地方 不可能 达到 (-1, -1) 来自 (x, y) 通过重复向上、向下、向左或向右移动 1 ,无需经过放置棋子的坐标。

更准确地说,计算格点的数量 (x, y) 没有放置石头的地方,并且有 不 存在整数对的有限序列 (x_0, y_0), \ldots, (x_k, y_k) 满足以下所有四个条件:

  • (x_0, y_0) = (x, y).
  • (x_k, y_k) = (-1, -1).
  • |x_i - x_{i+1}| + |y_i - y_{i+1}| = 1 对于所有人 0 \leq i < k.
  • 没有石头 (x_i, y_i) 对于所有人 0 \leq i \leq k.

约束

  • 0 \leq N \leq 2 \times 10^5
  • 0 \leq X_i, Y_i \leq 2 \times 10^5
  • 对 (X_i, Y_i) 是不同的。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
X_1 Y_1
\vdots
X_N Y_N

输出

打印满足条件的格点数。


示例输入 1

5
1 0
0 1
2 3
1 2
2 1

示例输出 1

1

不可能到达 (-1, -1) 来自 (1, 1).


示例输入 2

0

示例输出 2

0

可能存在未放置棋子的情况。


示例输入 3

22
0 1
0 2
0 3
1 0
1 4
2 0
2 2
2 4
3 0
3 1
3 2
3 4
5 1
5 2
5 3
6 0
6 4
7 0
7 4
8 1
8 2
8 3

示例输出 3

6

这样的点有六点: (6, 1), (6, 2), (6, 3), (7, 1), (7, 2), (7, 3).