/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
以下のような、無限に広い六角形のグリッドがあります。最初、全てのマスは白です。
ある六角形のマスは 2 つの整数 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) を黒く塗りました。
黒いマスがいくつの連結成分をなすか求めてください。
ただし、ある 2 つの黒いマスが同じ連結成分に属するとは、この 2 つの黒いマスの間をいくつかの隣接する黒いマスを辿って移動できることを指します。
制約
- 入力は全て整数
- 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
高橋くんがマスを黒く塗った後、グリッドは下図の状態になります。
黒いマスがなす連結成分は以下の 3 つです。
- (-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
Score : 400 points
Problem Statement
We have an infinite hexagonal grid shown below. Initially, all squares are white.
A hexagonal cell is represented as (i,j) with two integers i and j.
Cell (i,j) is adjacent to the following six cells:
- (i-1,j-1)
- (i-1,j)
- (i,j-1)
- (i,j+1)
- (i+1,j)
- (i+1,j+1)
Takahashi has painted N cells (X_1,Y_1),(X_2,Y_2),\dots,(X_N,Y_N) black.
Find the number of connected components formed by the black cells.
Two black cells belong to the same connected component when one can travel between those two black cells by repeatedly moving to an adjacent black cell.
Constraints
- All values in the input are integers.
- 1 \le N \le 1000
- |X_i|,|Y_i| \le 1000
- The pairs (X_i,Y_i) are distinct.
Input
The input is given from Standard Input in the following format:
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Print the answer as an integer.
Sample Input 1
6 -1 -1 0 1 0 2 1 0 1 2 2 0
Sample Output 1
3
After Takahashi paints cells black, the grid looks as shown below.
The black squares form the following three connected components:
- (-1,-1)
- (1,0),(2,0)
- (0,1),(0,2),(1,2)
Sample Input 2
4 5 0 4 1 -3 -4 -2 -5
Sample Output 2
4
Sample Input 3
5 2 1 2 -1 1 0 3 1 1 -1
Sample Output 3
1