103616: [Atcoder]ABC361 G - Go Territory

Problem Statement

There are $N$ stones placed on a $2$-dimensional plane. The $i$-th stone is located at coordinates $(X_i, Y_i)$. All stones are located at lattice points in the first quadrant (including the axes).

Count the number of lattice points $(x, y)$ where no stone is placed and it is impossible to reach $(-1, -1)$ from $(x, y)$ by repeatedly moving up, down, left, or right by $1$ without passing through coordinates where a stone is placed.

More precisely, count the number of lattice points $(x, y)$ where no stone is placed, and there does not exist a finite sequence of integer pairs $(x_0, y_0), \ldots, (x_k, y_k)$ that satisfies all of the following four conditions:

• $(x_0, y_0) = (x, y)$.
• $(x_k, y_k) = (-1, -1)$.
• $|x_i - x_{i+1}| + |y_i - y_{i+1}| = 1$ for all $0 \leq i < k$.
• There is no stone at $(x_i, y_i)$ for all $0 \leq i \leq k$.

Constraints

• $0 \leq N \leq 2 \times 10^5$
• $0 \leq X_i, Y_i \leq 2 \times 10^5$
• The pairs $(X_i, Y_i)$ are distinct.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$X_1$ $Y_1$
$\vdots$
$X_N$ $Y_N$

Output

Print the number of lattice points that satisfy the conditions.

Sample Input 1

5
1 0
0 1
2 3
1 2
2 1

Sample Output 1

1

It is impossible to reach $(-1, -1)$ from $(1, 1)$.

Sample Input 2

0

Sample Output 2

0

There may be cases where no stones are placed.

Sample Input 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

Sample Output 3

6

There are six such points: $(6, 1), (6, 2), (6, 3), (7, 1), (7, 2), (7, 3)$.

问题陈述

在二维平面上放置了N块石头。第i块石头位于坐标$(X_i, Y_i)$。所有石头都位于第一象限的格点上（包括坐标轴上）。

计算没有放置石头且无法通过重复向上、向下、向左或向右移动1个单位而不经过放置石头的坐标到达$(-1, -1)$的格点$(x, y)$的数量。

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

• $(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)$上没有石头。

约束条件

• $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)$。