Day 068-Q2 — 平面上の最近点対問題（分割統治 $O(N \log N)$）

問題

平面上に $N$ 点 $(x_i, y_i)$ が与えられる。$Q$ 個のクエリに対し、先頭 $k$ 点（$k$ はクエリで与えられる）における最近点対のユークリッド距離の2乗を出力せよ。

入出力例

5 3
0 0
3 4
1 1
6 1
4 3
2
3
5

25
2
2

k=2: (0,0),(3,4) → $9+16=25$。k=3: (0,0),(1,1) → $1+1=2$。k=5: (0,0)-(1,1) or (1,1)-(0,0) → 2。

概念図: 分割統治法の「中線ストリップ」

ヒント（段階的開示）

def closest_rec(pts):
    n = len(pts)
    if n <= 3:
        return min(dist2(pts[i],pts[j])
                   for i in range(n) for j in range(i+1,n))
    mid = n // 2
    mid_x = pts[mid][0]
    d = min(closest_rec(pts[:mid]), closest_rec(pts[mid:]))
    # ストリップ: (x - mid_x)^2 < d
    strip = sorted([p for p in pts if (p[0]-mid_x)**2 < d],
                   key=lambda p: p[1])
    i = 0
    while i < len(strip):
        j = i + 1
        while j < len(strip) and (strip[j][1]-strip[i][1])**2 < d:
            d = min(d, dist2(strip[i], strip[j]))
            j += 1
        i += 1
    return d

模範解答 (Python)

コピーimport sys
input = sys.stdin.readline

def dist2(a, b):
    return (a[0]-b[0])**2 + (a[1]-b[1])**2

def closest_strip(strip, d):
    n = len(strip)
    for i in range(n):
        j = i + 1
        while j < n and (strip[j][1] - strip[i][1])**2 < d:
            d = min(d, dist2(strip[i], strip[j]))
            j += 1
    return d

def closest_rec(pts):
    n = len(pts)
    if n <= 3:
        best = float('inf')
        for i in range(n):
            for j in range(i+1, n):
                best = min(best, dist2(pts[i], pts[j]))
        return best
    mid = n // 2
    mid_x = pts[mid][0]
    d = min(closest_rec(pts[:mid]), closest_rec(pts[mid:]))
    strip = []
    for p in pts:
        if (p[0] - mid_x)**2 < d:
            strip.append(p)
    strip.sort(key=lambda p: p[1])
    return closest_strip(strip, d)

def main():
    sys.setrecursionlimit(200000)
    N, Q = map(int, input().split())
    pts = []
    for _ in range(N):
        x, y = map(int, input().split())
        pts.append((x, y))

    queries = []
    for qi in range(Q):
        k = int(input())
        queries.append((k, qi))

    ans = [0] * Q
    for k, qi in queries:
        sub = sorted(pts[:k], key=lambda p: p[0])
        ans[qi] = closest_rec(sub)

    print('\n'.join(map(str, ans)))

main()

Step-by-Step 解説

Step 1: 基本的な分割統治

x座標でソート後、中央で左右に分割。左右それぞれ再帰的に最近点対距離 $d_L$, $d_R$ を求め、$d = \min(d_L, d_R)$ を得る。

Step 2: ストリップの処理

中線 $x = m$ から $\sqrt{d}$ 以内の点だけがクロス最近点対の候補。y座標でソートし、y差が $d$（2乗）を超えたら比較を打ち切る。幾何学的に各点の比較相手は最大7点以下であることが証明されており、ストリップ処理全体で $O(N)$。

Step 3: 整数演算の徹底

ストリップ条件 (p[0]-mid_x)**2 < d と y比較 (strip[j][1]-strip[i][1])**2 < d をいずれも距離の2乗で比較することで、sqrt を一切使わず浮動小数点誤差ゼロを実現。

Step 4: 計算量

よくあるミス

次のステップ

発展問題: 動的点追加で最近点対を維持する（Randomized Incremental または KD-Tree による動的版）。3次元空間への拡張。

自己評価