Go Territory

题目描述

平面上有 $N$ 块石头。第 $i$ 块石头位于坐标 $(X_i, Y_i)$。所有石头都位于第一象限的格点上（包括坐标轴）。 计算满足以下条件的格点 $(x, y)$ 的个数：该点处没有石头，并且不能通过反复向上、向下、向左或向右移动 $1$ 而不经过有石头的坐标从 $(x, y)$ 到达 $(-1, -1)$。 更精确地说，计算满足下列条件的格点 $(x, y)$ 的个数：该点处没有石头，并且不存在一个有限的整数对序列 $(x_0, y_0), \ldots, (x_k, y_k)$ 满足下面四个条件中的全部：

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

输入格式

输入按下列格式由标准输入提供： $N$ $X_1$ $Y_1$ $\vdots$ $X_N$ $Y_N$

输出格式

输出满足条件的格点的个数。

5
1 0
0 1
2 3
1 2
2 1

1

0

0

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

6

提示

$0 \leq N \leq 2 \times 10^5$ $0 \leq X_i, Y_i \leq 2 \times 10^5$ 各对 $(X_i, Y_i)$ 两两不同。 所有输入值均为整数。无法从 $(1, 1)$ 到达 $(-1, -1)$。
可能存在没有放置任何石头的情况。
这样的点有六个：$(6, 1), (6, 2), (6, 3), (7, 1), (7, 2), (7, 3)$。

标签: AtCoder|abc361G

来源

AtCoder|abc361G