D - 六边形网格的使用

分数：400分

问题描述

我们有一个无限的六边形网格，如下图所示。初始时，所有格子都是白色的。 六边形网格中的每个格子用两个整数$i$和$j$表示为$(i,j)$。格子$(i,j)$与以下六个格子相邻：

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

高桥君将$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)$对都是不同的。

输入

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

NX_1Y_1X_2Y_2\vdotsX_NY_N

输出

输出一个整数作为答案。

样例输入1

6

-1 -1

0 1

0 2

1 0

1 2

2 0

样例输出1

3

高桥君将格子涂黑后，网格如下图所示。 黑色格子形成了以下三个连通块：

• $(-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