G - Go Territory Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

2 次元平面上に N 個の石が置かれています。i 番目の石は座標 (X_i,Y_i) にあります。石は全て第一象限(軸上含む)の格子点にあります。

石の置かれていない格子点 (x,y) であって、上下左右のいずれかに 1 移動することを繰り返すことで、石の置かれている座標を通らずに (-1,-1) に到達することができないものの個数を求めてください。

より正確には、石の置かれていない格子点 (x,y) であって、以下の 4 条件を全て満たすような整数の組の有限列 (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) に石はない

制約

  • 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

石が 1 つも置かれていないこともあります。

入力例 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) の 6 個が該当します。

Score : 600 points

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).