围棋领地

题目描述

在二维平面上放置了 $N$ 颗棋子。第 $i$ 颗棋子位于坐标 $(X_i, Y_i)$。所有棋子都位于第一象限(含坐标轴)的格点上。

数出满足以下条件的格点 $(x, y)$ 的个数:该点没有放置棋子,且从 $(x, y)$ 出发,每次向上、下、左、右移动 $1$,且不经过放置了棋子的坐标,无法到达 $(-1, -1)$。

更准确地说,数出没有放置棋子、且不存在满足以下四个条件的有限整数对序列 $(x_0, y_0), \ldots, (x_k, y_k)$ 的格点 $(x, y)$ 的个数:

1. $(x_0, y_0) = (x, y)$。
2. $(x_k, y_k) = (-1, -1)$。
3. 对所有 $0 \leq i \lt k$,$|x_i - x_{i+1}| + |y_i - y_{i+1}| = 1$。
4. 对所有 $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

从 $(1, 1)$ 无法到达 $(-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

这样的点共有 6 个:$(6, 1), (6, 2), (6, 3), (7, 1), (7, 2), (7, 3)$。

数据范围

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