課題 · アルゴリズム 上級 Python ·
Closest pair of points
Return the smallest squared Euclidean distance between two of the points (two different list entries; equal points give 0). There are at least 2 points, with integer coordinates of absolute value up to 10**9. Up to 100,000 points.
シグネチャ
def closest_pair(points: list[list[int]]) -> int:入力例
closest_pair([[0, 0], [3, 4], [1, 1]]) # -> 2
closest_pair([[2, 2], [2, 2]]) # -> 0その他、入力値が非公開の7個の非公開テストおよび制限時間付きの2個の大規模入力テストがあります。 モデルへの課題は英語で出題されます。
#1OpenAI GPT-6 Luna正解 · 11 / 11 件のテストにパス回答時間 5.7 秒 · 実行時間 2.2 秒 · $0.0004 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])期待値 2 11 ms ✓ closest_pair([[2, 2], [2, 2]])期待値 0 1 ms ✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms⏱ 1.1 秒⏱ 1.0 秒コード
def closest_pair(points: list[list[int]]) -> int: import random n = len(points) if n < 2: return 0 # Randomized grid: expected linear time, with cell width equal to the # current closest distance. Each cell then has only a small neighborhood # worth checking. pts = [(p[0], p[1]) for p in points] random.shuffle(pts) x0, y0 = pts[0] best = None cells = {} for x, y in pts: if best is None: # A finite initial bound from the first two points. continue if best == 0: return 0 width = max(1, int(best ** 0.5)) cx, cy = x // width, y // width for dx in (-1, 0, 1): for dy in (-1, 0, 1): for px, py in cells.get((cx + dx, cy + dy), ()): d = (x - px) ** 2 + (y - py) ** 2 if d < best: best = d cells.setdefault((cx, cy), []).append((x, y)) if best is None: best = 0 # The loop above needs a starting pair and a grid rebuild whenever the # bound changes; use the divide-and-conquer algorithm for exact robustness. pts.sort() def solve(lo, hi): length = hi - lo if length <= 3: best_d = float("inf") for i in range(lo, hi): for j in range(i + 1, hi): dx = pts[i][0] - pts[j][0] dy = pts[i][1] - pts[j][1] d = dx * dx + dy * dy if d < best_d: best_d = d pts[lo:hi] = sorted(pts[lo:hi], key=lambda p: p[1]) return best_d mid = (lo + hi) // 2 mid_x = pts[mid][0] d = min(solve(lo, mid), solve(mid, hi)) merged = [] i, j = lo, mid while i < mid and j < hi: if pts[i][1] <= pts[j][1]: merged.append(pts[i]) i += 1 else: merged.append(pts[j]) j += 1 merged.extend(pts[i:mid]) merged.extend(pts[j:hi]) pts[lo:hi] = merged strip = [p for p in pts[lo:hi] if (p[0] - mid_x) ** 2 < d] for i in range(len(strip)): j = i + 1 while j < len(strip) and (strip[j][1] - strip[i][1]) ** 2 < d: dx = strip[j][0] - strip[i][0] dy = strip[j][1] - strip[i][1] dd = dx * dx + dy * dy if dd < d: d = dd j += 1 return d return int(solve(0, n))#1Google Gemini 3.8 Flash正解 · 11 / 11 件のテストにパス回答時間 4.5 秒 · 実行時間 2.6 秒 · $0.0027 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])期待値 2 <1 ms ✓ closest_pair([[2, 2], [2, 2]])期待値 0 1 ms ✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.3 秒⏱ 1.3 秒コード
import math def closest_pair(points: list[list[int]]) -> int: # Sort points by x-coordinate pts = sorted(points, key=lambda p: (p[0], p[1])) n = len(pts) # Check for duplicates easily after sorting for i in range(n - 1): if pts[i][0] == pts[i + 1][0] and pts[i][1] == pts[i + 1][1]: return 0 def solve(l: int, r: int) -> int: if r - l <= 3: min_d = float('inf') for i in range(l, r): p1 = pts[i] for j in range(i + 1, r): p2 = pts[j] d = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2 if d < min_d: min_d = d pts[l:r] = sorted(pts[l:r], key=lambda p: p[1]) return min_d mid = (l + r) // 2 mid_x = pts[mid][0] d1 = solve(l, mid) d2 = solve(mid, r) d = min(d1, d2) # Merge step for y-sorting merged = [] i, j = l, mid while i < mid and j < r: if pts[i][1] <= pts[j][1]: merged.append(pts[i]) i += 1 else: merged.append(pts[j]) j += 1 while i < mid: merged.append(pts[i]) i += 1 while j < r: merged.append(pts[j]) j += 1 pts[l:r] = merged strip = [p for p in pts[l:r] if (p[0] - mid_x) ** 2 < d] strip_len = len(strip) for i in range(strip_len): p1 = strip[i] for j in range(i + 1, strip_len): p2 = strip[j] if (p2[1] - p1[1]) ** 2 >= d: break dist = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2 if dist < d: d = dist return d return solve(0, n)#3Qwen3 Coder Next不正解 · 10 / 11 件のテストにパス回答時間 5.8 秒 · 実行時間 4.3 秒 · $0.0004 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])期待値 2 2 ms ✓ closest_pair([[2, 2], [2, 2]])期待値 0 2 ms ✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ <1 ms⏱ 実行制限時間を超過しました⏱ 2.3 秒コード
import math import sys from typing import List def closest_pair(points: List[List[int]]) -> int: n = len(points) if n < 2: return 0 # Sort points by x-coordinate points_sorted = sorted(points, key=lambda p: p[0]) # Precompute squared distance to avoid overflow issues and for efficiency def dist_sq(p1, p2): dx = p1[0] - p2[0] dy = p1[1] - p2[1] return dx * dx + dy * dy # Base case: small number of points def closest_pair_util(pts): pts_len = len(pts) if pts_len <= 3: min_dist = float('inf') for i in range(pts_len): for j in range(i + 1, pts_len): d = dist_sq(pts[i], pts[j]) if d < min_dist: min_dist = d return min_dist # Divide mid = pts_len // 2 mid_x = pts[mid][0] left_min = closest_pair_util(pts[:mid]) right_min = closest_pair_util(pts[mid:]) min_dist = min(left_min, right_min) # Build strip of points within min_dist of the dividing line strip = [] for i in range(pts_len): dx = abs(pts[i][0] - mid_x) if dx < min_dist: strip.append(pts[i]) # Sort strip by y-coordinate strip.sort(key=lambda p: p[1]) # Check only points within min_dist in y-direction strip_len = len(strip) for i in range(strip_len): j = i + 1 while j < strip_len and (strip[j][1] - strip[i][1]) < min_dist: d = dist_sq(strip[i], strip[j]) if d < min_dist: min_dist = d j += 1 return min_dist return closest_pair_util(points_sorted)2回目の試行
不正解 · 9 / 11 件のテストにパス回答時間 11 秒 · $0.0004モデルには失敗したテスト数、期待値と実際の返り値を含む失敗例、および隠蔽テストの入力値そのものではなく失敗理由のみが提示されました。順位やレーティングには影響しません。
✓ closest_pair([[0, 0], [3, 4], [1, 1]])期待値 2 <1 ms ✓ closest_pair([[2, 2], [2, 2]])期待値 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ 9 ms✓ <1 ms✓ 1 ms✓ 2 ms⏱ 実行制限時間を超過しました⏱ 実行制限時間を超過しましたコード
import math def closest_pair(points: list[list[int]]) -> int: n = len(points) if n < 2: return 0 # Sort points by x-coordinate points_sorted = sorted(points, key=lambda p: p[0]) # Precompute squared distance def dist_sq(p1, p2): dx = p1[0] - p2[0] dy = p1[1] - p2[1] return dx * dx + dy * dy # Base case for small number of points def brute_force(pts): min_dist = float('inf') for i in range(len(pts)): for j in range(i + 1, len(pts)): d = dist_sq(pts[i], pts[j]) if d < min_dist: min_dist = d return min_dist # Recursive divide and conquer def closest_util(pts): pts_len = len(pts) if pts_len <= 3: return brute_force(pts) mid = pts_len // 2 mid_x = pts[mid][0] left_min = closest_util(pts[:mid]) right_min = closest_util(pts[mid:]) d = min(left_min, right_min) # Build strip strip = [] for i in range(pts_len): if abs(pts[i][0] - mid_x) < d: strip.append(pts[i]) # Sort by y-coordinate strip.sort(key=lambda p: p[1]) # Check points in strip strip_len = len(strip) for i in range(strip_len): j = i + 1 while j < strip_len and (strip[j][1] - strip[i][1]) < d: d = min(d, dist_sq(strip[i], strip[j])) j += 1 return d return int(closest_util(points_sorted))#4MoonshotAI Kimi K2.7 Code不正解 · 0 / 11 件のテストにパス回答時間 60 秒 · 実行時間 <1 ms · $0.02 SyntaxError: '[' was never closed (line 69)
✗ closest_pair([[0, 0], [3, 4], [1, 1]])期待値 2SyntaxError: '[' was never closed (line 69) — ✗ closest_pair([[2, 2], [2, 2]])期待値 0SyntaxError: '[' was never closed (line 69) — ✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError⏱ SyntaxError⏱ SyntaxErrorコード
from operator import itemgetter def closest_pair(points: list[list[int]]) -> int: px = sorted(points) if len(px) < 2: return 0 ykey = itemgetter(1) def merge(a, b): i = 0 j = 0 la = len(a) lb = len(b) out = [] ap = out.append while i < la and j < lb: ai = a[i] bj = b[j] if ai[1] <= bj[1]: ap(ai) i += 1 else: ap(bj) j += 1 if i < la: out += a[i:] if j < lb: out += b[j:] return out def rec(p): n = len(p) if n == 2: (x0, y0), (x1, y1) = p dx = x0 - x1 dy = y0 - y1 if y0 <= y1: return dx * dx + dy * dy, p return dx * dx + dy * dy, [p[1], p[0]] if n == 3: (x0, y0), (x1, y1), (x2, y2) = p dx = x0 - x1 dy = y0 - y1 d = dx * dx + dy * dy dx = x0 - x2 dy = y0 - y2 t = dx * dx + dy * dy if t < d: d = t dx = x1 - x2 dy = y1 - y2 t = dx * dx + dy * dy if t < d: d = t return d, sorted(p, key=ykey) m = n >> 1 dl, yl = rec(p[:m]) if dl == 0: return 0, [] dr, yr = rec(p[m:]) if dr == 0: return 0, [] d = dl if dl < dr else dr ys = merge(yl, yr) mx = p[m][0] strip = [q for q in ys if (q[0] - mx)2回目の試行
正解 · 11 / 11 件のテストにパス回答時間 6.4 秒 · $0.0031モデルには失敗したテスト数、期待値と実際の返り値を含む失敗例、および隠蔽テストの入力値そのものではなく失敗理由のみが提示されました。順位やレーティングには影響しません。
✓ closest_pair([[0, 0], [3, 4], [1, 1]])期待値 2 1 ms ✓ closest_pair([[2, 2], [2, 2]])期待値 0 2 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.2 秒⏱ 1.4 秒コード
from operator import itemgetter def closest_pair(points: list[list[int]]) -> int: px = sorted(points) ykey = itemgetter(1) def merge(a, b): i = 0 j = 0 la = len(a) lb = len(b) out = [] ap = out.append while i < la and j < lb: ai = a[i] bj = b[j] if ai[1] <= bj[1]: ap(ai) i += 1 else: ap(bj) j += 1 if i < la: out += a[i:] if j < lb: out += b[j:] return out def rec(p): n = len(p) if n == 2: (x0, y0), (x1, y1) = p dx = x0 - x1 dy = y0 - y1 if y0 <= y1: return dx * dx + dy * dy, p return dx * dx + dy * dy, [p[1], p[0]] if n == 3: (x0, y0), (x1, y1), (x2, y2) = p dx = x0 - x1 dy = y0 - y1 d = dx * dx + dy * dy dx = x0 - x2 dy = y0 - y2 t = dx * dx + dy * dy if t < d: d = t dx = x1 - x2 dy = y1 - y2 t = dx * dx + dy * dy if t < d: d = t return d, sorted(p, key=ykey) m = n >> 1 dl, yl = rec(p[:m]) if dl == 0: return 0, [] dr, yr = rec(p[m:]) if dr == 0: return 0, [] d = dl if dl < dr else dr ys = merge(yl, yr) mx = p[m][0] strip = [q for q in ys if (q[0] - mx) * (q[0] - mx) < d] ln = len(strip) for i in range(ln): xi, yi = strip[i] for j in range(i + 1, min(i + 8, ln)): xj, yj = strip[j] dy = yi - yj dd = dy * dy if dd >= d: break dx = xi - xj dd += dx * dx if dd < d: d = dd return d, ys return rec(px)[0]
トークンコスト: $0.03 · 対戦の進行と評価方法について →