Day 117-Q4 — 3次元最近点対問題（分割統治法）

2026-08-09 赤色 Master / Phase 8+ ★★★★★★★★★ 高度幾何・分割統治・平面走査の3次元拡張

問題

3次元空間上に $N$ 個の点が与えられる。全ての点対の中で、ユークリッド距離が最小となる組を求め、その距離の2乗を出力せよ（座標は整数なので距離の2乗も必ず整数になる）。

入力形式

N
x_1 y_1 z_1
x_2 y_2 z_2
:
x_N y_N z_N

制約

$2 \le N \le 2\times10^4$
$-10^9 \le x_i, y_i, z_i \le 10^9$
全ての点は相異なる

入出力例

入力例1

5
0 0 0
3 4 0
3 0 4
1 1 1
5 5 5

出力例1

3

入力例2

2
0 0 0
1000000000 1000000000 1000000000

出力例2

3000000000000000000

入力例1: 点 $(0,0,0)$ と $(1,1,1)$ の距離の2乗が $1^2+1^2+1^2=3$ で最小。

概念図: 分割統治の帯（strip）探索

x座標で左右分割 → 分割線付近の帯だけをyでソートして比較 左半分（再帰的に d_L を求める） 右半分（再帰的に d_R を求める） 帯（strip）: |x - mid_x| < d = min(d_L, d_R) 帯内の点をy座標でソートし、yの差がd未満の隣接点同士だけ3次元距離を直接比較する。

ヒント（段階的開示）

ヒント1: 方向性
全点対を調べれば $O(N^2)$ だが、$N$ が大きいと間に合わない。2次元平面上の最近点対問題を分割統治で $O(N\log N)$ に落とすアルゴリズムを知っているなら、その考え方をそのまま3次元へ拡張できないか考える。「$x$座標でソートして半分に分割し、それぞれを再帰的に解いた上で、分割線をまたぐペアだけを追加で調べる」という骨格は次元が変わっても同じ。
ヒント2: アプローチ
$x$座標の中央値で左右に分割し、それぞれの最小距離 $d_L, d_R$ を再帰的に求め、$d=\min(d_L,d_R)$ とする。次に、分割線から $x$方向の距離が $d$ 未満の点だけを集めた「帯（strip）」を作り、帯の中の点を $y$座標でソートして、$y$座標の差が $d$ 未満の点同士だけを総当たりで比較する。
ヒント3: 誘導（コード骨格） 
# rec(pts):  pts は x座標でソート済み
#   len(pts) <= 3 なら愚直に全ペア距離2乗の最小値を返す
#   mid = len(pts)//2 で左右に分割し d = min(rec(左), rec(右))
#   strip = [p for p in pts if (p.x - pts[mid].x)**2 < d]
#   strip を y座標でソートし、隣接する点同士を
#   (差のy座標)**2 < d の範囲で総当たりチェックして d を更新
#   最後に d を返す

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    pts = []
    for _ in range(n):
        x = int(data[idx]); y = int(data[idx + 1]); z = int(data[idx + 2])
        idx += 3
        pts.append((x, y, z))

    pts.sort(key=lambda p: p[0])

    def brute(pts):
        best = float('inf')
        m = len(pts)
        for i in range(m):
            for j in range(i + 1, m):
                dx = pts[i][0] - pts[j][0]
                dy = pts[i][1] - pts[j][1]
                dz = pts[i][2] - pts[j][2]
                d = dx * dx + dy * dy + dz * dz
                if d < best:
                    best = d
        return best

    def rec(pts):
        m = len(pts)
        if m <= 3:
            return brute(pts)
        mid = m // 2
        midx = pts[mid][0]
        d = min(rec(pts[:mid]), rec(pts[mid:]))

        strip = [p for p in pts if (p[0] - midx) ** 2 < d]
        strip.sort(key=lambda p: p[1])
        s = len(strip)
        for i in range(s):
            j = i + 1
            while j < s and (strip[j][1] - strip[i][1]) ** 2 < d:
                dx = strip[i][0] - strip[j][0]
                dy = strip[i][1] - strip[j][1]
                dz = strip[i][2] - strip[j][2]
                dist = dx * dx + dy * dy + dz * dz
                if dist < d:
                    d = dist
                j += 1
        return d

    print(rec(pts))


solve()
計算量: 各再帰レベルで帯内の点を$y$座標でソートする実装のため $O(N\log^2 N)$（マージソート的に$y$順を引き継ぐ実装にすれば $O(N\log N)$ に改善可能）。入力例1・2、および300ケースのランダム点群に対する $O(N^2)$ 全探索との比較で正しさを検証済み。

Step-by-Step 解説

1$x$座標でソートして分割
全点を$x$座標でソートし、中央で左右に分割する。左右それぞれの最小距離を独立な部分問題として再帰的に解く。
2帯（strip）の抽出
左右の最小距離のうち小さい方を$d$とする。答えとなるペアが左右をまたぐ場合、そのペアの$x$座標の差は$d$未満でなければならない。分割線から$x$距離が$\sqrt d$未満の点だけを集めた帯を作る。
3帯内を$y$座標でソートして絞り込み
帯の中の点を$y$座標でソートし、$y$座標の差が$\sqrt d$未満の範囲だけを総当たりで調べる。空間充填の議論により内側ループは償却定数回で抑えられる。
4実際の距離計算は$z$座標も含めて3次元で
帯の絞り込みは$x,y$の2軸だけで行うが、最終的な距離判定では必ず$z$座標の差も含めて3次元ユークリッド距離で比較する。
5計算量の確認
$N\le2\times10^4$程度なら$O(N\log^2 N)$でも十分高速。$O(N^2)$の愚直解はPythonでは現実的な時間で終わらない。

よくあるミス

ミス原因正しい書き方
帯の絞り込みに$z$座標も条件に入れてしまう2次元アルゴリズムの単純な機械的拡張だと誤解する帯の絞り込みは分割軸（$x$）と走査軸（$y$）のみで行い、最終判定でのみ$z$を含める
距離をsqrtで計算して比較してしまう座標が整数なら実数比較は不要という点を見落とす距離の2乗（整数）のまま比較すれば浮動小数点誤差を避けられる
帯の中の点をソートせず全探索してしまう「帯内でも全点対を調べれば正しい」という考えのまま最適化を忘れる$y$座標でソートしてから隣接点のみ調べないと計算量が$O(N^2)$に戻る
再帰の基底ケースを$m\le1$にしてしまう「2点未満なら比較不要」という考えに寄りすぎる$m\le3$を基底ケースにするのが定石

次のステップ

  • 発展: 帯内のソートをマージソートの併合過程に組み込み、真の$O(N\log N)$に高速化する
  • 次回予告: DSU on Tree（small-to-largeマージ）による部分木の相異なる値の個数集計

自己評価

自分の回答

気づき・メモ