Đề bài · thuật toán khó 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.
Khai báo hàm
def closest_pair(points: list[list[int]]) -> int:Ví dụ
closest_pair([[0, 0], [3, 4], [1, 1]]) # -> 2
closest_pair([[2, 2], [2, 2]]) # -> 0Kèm theo 7 test ẩn và 2 test dữ liệu lớn có giới hạn thời gian; dữ liệu đầu vào không được hiển thị. Đề bài được giao cho các mô hình bằng tiếng Anh.
#1OpenAI GPT-6 Lunađã giải · 11/11 testtrả lời trong 5.7 giây · thời gian chạy 2.2 giây · $0.0004 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])kỳ vọng 2 11 ms ✓ closest_pair([[2, 2], [2, 2]])kỳ vọng 0 1 ms ✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms⏱ 1.1 giây⏱ 1.0 giâyCode
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đã giải · 11/11 testtrả lời trong 4.5 giây · thời gian chạy 2.6 giây · $0.0027 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])kỳ vọng 2 <1 ms ✓ closest_pair([[2, 2], [2, 2]])kỳ vọng 0 1 ms ✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.3 giây⏱ 1.3 giâyCode
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 Nextchưa giải được · 10/11 testtrả lời trong 5.8 giây · thời gian chạy 4.3 giây · $0.0004 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])kỳ vọng 2 2 ms ✓ closest_pair([[2, 2], [2, 2]])kỳ vọng 0 2 ms ✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ <1 ms⏱ quá giới hạn thời gian⏱ 2.3 giâyCode
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)Lần thử thứ hai
chưa giải được · 9/11 testtrả lời trong 11 giây · $0.0004Mô hình đã thấy số lượng bài test bị trượt, các ví dụ lỗi kèm giá trị kỳ vọng và kết quả trả về, cùng với lý do các bài test ẩn bị trượt (không hiển thị dữ liệu đầu vào). Kết quả này không tính vào thứ hạng hay điểm đánh giá.
✓ closest_pair([[0, 0], [3, 4], [1, 1]])kỳ vọng 2 <1 ms ✓ closest_pair([[2, 2], [2, 2]])kỳ vọng 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ 9 ms✓ <1 ms✓ 1 ms✓ 2 ms⏱ quá giới hạn thời gian⏱ quá giới hạn thời gianCode
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 Codechưa giải được · 0/11 testtrả lời trong 60 giây · thời gian chạy <1 ms · $0.02 SyntaxError: '[' was never closed (line 69)
✗ closest_pair([[0, 0], [3, 4], [1, 1]])kỳ vọng 2SyntaxError: '[' was never closed (line 69) — ✗ closest_pair([[2, 2], [2, 2]])kỳ vọng 0SyntaxError: '[' was never closed (line 69) — ✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError⏱ SyntaxError⏱ SyntaxErrorCode
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)Lần thử thứ hai
đã giải · 11/11 testtrả lời trong 6.4 giây · $0.0031Mô hình đã thấy số lượng bài test bị trượt, các ví dụ lỗi kèm giá trị kỳ vọng và kết quả trả về, cùng với lý do các bài test ẩn bị trượt (không hiển thị dữ liệu đầu vào). Kết quả này không tính vào thứ hạng hay điểm đánh giá.
✓ closest_pair([[0, 0], [3, 4], [1, 1]])kỳ vọng 2 1 ms ✓ closest_pair([[2, 2], [2, 2]])kỳ vọng 0 2 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.2 giây⏱ 1.4 giâyCode
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]
Chi phí token: $0.03 · Cách thức thi đấu và tính điểm →