← 返回题目列表

AtCoder · abc269_d

G. 一定要使用六边形网格

中文机器翻译题面 查看原题

分数: 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) 是不同的。

输入

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

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

Takahashi 将单元格涂成黑色后,网格如下所示。

黑色方块形成以下三个连通分量:

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