ABC269D - Do use hexagon grid

考え方

すべての点の組み合わせをみて，隣接しているものをUnionFind（UnionFind木 - 競プロはじめました）でマージすれば良い．

2点$(x_{1}, y_{1}), (x_{2}, y_{2})$の隣接条件は

\begin{aligned}
\begin{cases}
\, \max(|x_{1} - x_{2}|, |y_{1} - y_{2}|) = 1 \\
\, \dfrac{y_{1} - y_{2}}{x_{1} - x_{2}} \neq -1
\end{cases}
\end{aligned}

と表せる（1つめが8近傍の条件，2つ目が傾きが-1でないこと）．

回答例

N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]

# --- UnionFind ---
p = [-1] * (N + 1)
def root(x):
  if p[x] < 0:
    return x
  p[x] = root(p[x])
  return p[x]
 
def unite(x, y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  p[x] += p[y]
  p[y] = x
# --- UnionFind ---

for i in range(N):
    x1, y1 = X[i]
    for j in range(i, N):
        x2, y2 = X[j]
        if (max(abs(x1 - x2), abs(y1- y2)) == 1 and (y1 - y2) != - (x1 - x2)):
            unite(i, j)

memo = set()
for i in range(N):
    r = root(i)
    if r not in memo:
        memo.add(r)

print(len(memo))