問題
平面上に$N$個の相異なる点が与えられる。すべての点対の中で、ユークリッド距離の2乗が最小となる値を求めよ。
入力形式
N
x_1 y_1
x_2 y_2
...
x_N y_N制約
$2 \le N \le 200000$
$0 \le x_i, y_i \le 10^9$
入出力例
入力例1
6
2 3
12 30
40 50
5 1
12 10
3 4出力例1
2点(2,3)と(3,4)の距離2乗は(3-2)²+(4-3)²=1+1=2で全点対中最小。
概念図
ヒント（段階的開示）
ヒント1（方向性）
全点対総当たりはO(N²)。x座標でソートし左右に分割、それぞれ再帰的に最近点対を求める分割統治の骨格はすぐ思いつく。問題は分割線をまたぐ点対の扱い。
ヒント2（アプローチ）
左右の最小距離2乗をdとする。分割線から横方向の距離が√d未満の点だけを集めた帯(strip)を作れば答えを更新しうる点対はこの帯の中にしかない。帯の中をy座標でソートすればy差が√d未満の相手は定数個(高々7個程度)しかないことが証明できる。
ヒント3（誘導）
def rec(pts_x):
if len(pts_x) <= 3:
return brute(pts_x)
mid = len(pts_x) // 2
midx = pts_x[mid][0]
dl = rec(pts_x[:mid])
dr = rec(pts_x[mid:])
d = min(dl, dr)
strip = [p for p in pts_x if (p[0] - midx) ** 2 < d]
strip.sort(key=lambda p: p[1])
for i in range(len(strip)):
for j in range(i + 1, min(i + 7, len(strip))):
d = min(d, dist2(strip[i], strip[j]))
return 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]); idx += 2
pts.append((x, y))
def dist2(a, b):
dx = a[0] - b[0]
dy = a[1] - b[1]
return dx * dx + dy * dy
def brute(pts_list):
best = float('inf')
m = len(pts_list)
for i in range(m):
for j in range(i + 1, m):
d = dist2(pts_list[i], pts_list[j])
if d < best:
best = d
return best
pts_x = sorted(pts)
def rec(lo, hi):
m = hi - lo
if m <= 3:
return brute(pts_x[lo:hi])
mid = lo + m // 2
midx = pts_x[mid][0]
dl = rec(lo, mid)
dr = rec(mid, hi)
d = min(dl, dr)
strip = [p for p in pts_x[lo:hi] if (p[0] - midx) ** 2 < d]
strip.sort(key=lambda p: p[1])
sm = len(strip)
for i in range(sm):
for j in range(i + 1, min(i + 7, sm)):
dd = dist2(strip[i], strip[j])
if dd < d:
d = dd
return d
print(rec(0, n))
solve()Step-by-Step 解説
1x座標での分割
点をx座標でソートし中央で左右に分ける。それぞれ再帰的に最近点対距離2乗を求める。点数3以下は総当たり。
点をx座標でソートし中央で左右に分ける。それぞれ再帰的に最近点対距離2乗を求める。点数3以下は総当たり。
2分割線をまたぐペアの絞り込み
d=min(dl,dr)が分かれば、更新しうるのは分割線からの水平距離が√d未満の点だけ。これをstripとして抽出。
d=min(dl,dr)が分かれば、更新しうるのは分割線からの水平距離が√d未満の点だけ。これをstripとして抽出。
3y座標ソートの理由
帯の中の点をy座標でソートしておくことで近い候補を連続範囲に集約できる。
帯の中の点をy座標でソートしておくことで近い候補を連続範囲に集約できる。
4内側ループを定数回で打ち切れる根拠
帯の幅は2√dしかなく、鳩の巣原理により同じ半分の点が同じd×d/2領域に2つ以上入ると矛盾する。よって高々6〜7個で打ち切ってよい。
帯の幅は2√dしかなく、鳩の巣原理により同じ半分の点が同じd×d/2領域に2つ以上入ると矛盾する。よって高々6〜7個で打ち切ってよい。
5計算量
T(N)=2T(N/2)+O(N log N)(帯のソート分)。y座標ソート済み配列をマージするようにすればO(N)に落とせ全体O(N log N)。本解答は簡単のためO(N log²N)だがN≤2×10^5なら十分高速。
T(N)=2T(N/2)+O(N log N)(帯のソート分)。y座標ソート済み配列をマージするようにすればO(N)に落とせ全体O(N log N)。本解答は簡単のためO(N log²N)だがN≤2×10^5なら十分高速。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 距離そのもの(平方根あり)で比較する | 浮動小数点誤差が混入し厳密比較が壊れる | 座標が整数なら距離の2乗のまま整数演算で比較し続ける |
| 内側ループを絞らず帯を全探索する | 定数個で打ち切れる根拠を知らない | min(i+7, sm)のように打ち切りを入れて計算量を担保する |
| 帯の判定で距離2乗と生の距離を混同する | 単位が揃っていない比較 | (p[0]-midx)**2 < dのように両辺を2乗のスケールで揃える |
| 基底ケースで点数2以下の時のminでエラー | 境界条件の考慮漏れ | 点数3以下は常にbruteに委ね内部でinfを返すようにする |
次のステップ
- 発展: 3次元以上に拡張した最近点対問題も同様の分割統治+帯絞り込みで解ける
- 次回予告: 次回のテーマは今後のセッションで選定