使用六边形网格

题目描述

我们有一个如下所示的无限六边形网格。初始时,所有格子都是白色。

六边形格子用两个整数 $(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)$ 涂成了黑色。

求黑色格子构成的连通分量的个数。

当可以从两个黑色格子中的一个出发,反复移动到相邻的黑色格子而到达另一个时,这两个黑色格子属于同一个连通分量。

输入格式

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

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

输出格式

输出答案(一个整数)。

样例

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

3

高桥君将格子涂黑后,网格如下所示。

黑色格子形成以下三个连通分量:

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

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

4

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

1

数据范围

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