AT_abc269_d [ABC269D] Do use hexagon grid

题目描述

有一个无限大的六边形网格。最初，所有的格子都是白色的。

一个六边形格子可以用两个整数 $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), \dots, (X_N, Y_N)$ 涂成了黑色。 请你求出黑色格子形成了多少个连通块。 这里，两个黑色格子属于同一个连通块，指的是可以通过若干个相邻的黑色格子从一个格子移动到另一个格子。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出一个整数，表示连通块的个数。

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

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

输出 #2

4

输入输出样例 #3

输入 #3

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

输出 #3

1

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 1000$
• $|X_i|, |Y_i| \leq 1000$
• $(X_i, Y_i)$ 两两不同。

样例解释 1

高桥君涂黑后的网格如下图所示。

黑色格子形成了如下 $3$ 个连通块：

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

由 ChatGPT 4.1 翻译