4228: Do use hexagon grid

# Do use hexagon grid ### 内存 1024MB ### 时间 2S ## 题目描述 我们有一个如下所示的无限大的六边形网格。最初，所有格子都是白色的。  一个六边形格子可以用两个整数 $i$ 和 $j$ 表示为 $(i,j)$。 格子 $(i,j)$ 与以下 6 个格子相邻: $(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),\cdots,(X_N,Y_N)$ 涂成黑色。 请求出黑色格子形成的连通分量的数量。 这里，如果两个黑色格子之间可以通过若干个相邻的黑色格子移动到达，则认为这两个黑色格子属于同一个连通分量。 ## 输入格式 输入按以下格式从标准输入给出: $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 ``` ### 输入样例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 ``` ## 数据范围与提示 【样例1说明】 小高将格子涂黑后，网格如下图所示。  黑色格子形成以下三个连通分量: (-1,-1) (1,0),(2,0) (0,1),(0,2),(1,2) 【数据范围】 输入中的所有值都是整数 $1 \le N \le 1000$ $|X_i|,|Y_i| \le 1000$ $(X_i,Y_i)$ 两两不同。 ## 题目来源 ABC269D