Do use hexagon grid

题目描述

我们有下述所示的无限六边形格子。最初，所有格子都是白色的。 一个六边形格子用两个整数 $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)$

Takahashi 已将 $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

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)$ 互不相同。Takahashi 将格子涂黑后，格子如下图所示。 黑色格子形成了下面的三个连通分量：

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

标签: AtCoder|abc269D

来源

AtCoder|abc269D