102693: [AtCoder]ABC269 D - Do use hexagon grid

Problem Statement

We have an infinite hexagonal grid shown below. Initially, all squares are white.

A hexagonal cell is represented as $(i,j)$ with two integers $i$ and $j$.
Cell $(i,j)$ is adjacent to the following six cells:

• $(i-1,j-1)$
• $(i-1,j)$
• $(i,j-1)$
• $(i,j+1)$
• $(i+1,j)$
• $(i+1,j+1)$

Takahashi has painted $N$ cells $(X_1,Y_1),(X_2,Y_2),\dots,(X_N,Y_N)$ black.
Find the number of connected components formed by the black cells.
Two black cells belong to the same connected component when one can travel between those two black cells by repeatedly moving to an adjacent black cell.

Constraints

• All values in the input are integers.
• $1 \le N \le 1000$
• $|X_i|,|Y_i| \le 1000$
• The pairs $(X_i,Y_i)$ are distinct.

Input

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

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

Output

Print the answer as an integer.

Sample Input 1

6
-1 -1
0 1
0 2
1 0
1 2
2 0

Sample Output 1

3

After Takahashi paints cells black, the grid looks as shown below.

The black squares form the following three connected components:

• $(-1,-1)$
• $(1,0),(2,0)$
• $(0,1),(0,2),(1,2)$

Sample Input 2

4
5 0
4 1
-3 -4
-2 -5

Sample Output 2

4

Sample Input 3

5
2 1
2 -1
1 0
3 1
1 -1

Sample Output 3

1

问题描述

我们有一个无限的六边形网格，如下所示。最初，所有的方格都是白色的。

一个六边形单元用两个整数i和j表示为$(i,j)$。

• $(i-1,j-1)$
• $(i-1,j)$
• $(i,j-1)$
• $(i,j+1)$
• $(i+1,j)$
• $(i+1,j+1)$

Takahashi已经将$N$个单元$(X_1,Y_1),(X_2,Y_2),\dots,(X_N,Y_N)$涂成了黑色。

找出由黑色单元组成的连通分量的数量。

当可以从两个黑色单元之间反复移动到相邻的黑色单元时，两个黑色单元属于同一个连通分量。

约束

• 输入中的所有值都是整数。
• $1 \le N \le 1000$
• $|X_i|,|Y_i| \le 1000$
• $(X_i,Y_i)$对是不同的。

输入

输入从标准输入以以下格式给出：

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

输出

打印一个整数作为答案。

样例输入 1

6
-1 -1
0 1
0 2
1 0
1 2
2 0

样例输出 1

3

在Takahashi将单元格涂成黑色后，网格看起来如下所示。

黑色方块形成了以下三个连通分量：

• $(-1,-1)$
• $(1,0),(2,0)$
• $(0,1),(0,2),(1,2)$

样例输入 2

4
5 0
4 1
-3 -4
-2 -5

样例输出 2

4

样例输入 3

5
2 1
2 -1
1 0
3 1
1 -1

样例输出 3

1