Tugas · algoritma sulit 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.
Tanda tangan
def closest_pair(points: list[list[int]]) -> int:Contoh
closest_pair([[0, 0], [3, 4], [1, 1]]) # -> 2
closest_pair([[2, 2], [2, 2]]) # -> 0Ditambah 7 pengujian tersembunyi dan 2 pengujian input besar dengan batas waktu; inputnya tidak ditampilkan. Tugas diberikan kepada model dalam bahasa Inggris.
#1OpenAI GPT-6 Lunaselesai · 11 dari 11 pengujianrespons dalam 5.7 dtk · waktu eksekusi 2.2 dtk · $0.0004 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])diharapkan 2 11 md ✓ closest_pair([[2, 2], [2, 2]])diharapkan 0 1 md ✓ <1 md✓ 1 md✓ <1 md✓ <1 md✓ 1 md✓ <1 md✓ <1 md⏱ 1.1 dtk⏱ 1.0 dtkKode
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 Flashselesai · 11 dari 11 pengujianrespons dalam 4.5 dtk · waktu eksekusi 2.6 dtk · $0.0027 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])diharapkan 2 <1 md ✓ closest_pair([[2, 2], [2, 2]])diharapkan 0 1 md ✓ <1 md✓ <1 md✓ 1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 1.3 dtk⏱ 1.3 dtkKode
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 Nexttidak selesai · 10 dari 11 pengujianrespons dalam 5.8 dtk · waktu eksekusi 4.3 dtk · $0.0004 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])diharapkan 2 2 md ✓ closest_pair([[2, 2], [2, 2]])diharapkan 0 2 md ✓ 1 md✓ 1 md✓ <1 md✓ <1 md✓ 2 md✓ <1 md✓ <1 md⏱ batas waktu terlampaui⏱ 2.3 dtkKode
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)Percobaan kedua
tidak selesai · 9 dari 11 pengujianrespons dalam 11 dtk · $0.0004Model melihat berapa banyak tes yang gagal, contoh yang gagal beserta nilai yang diharapkan dan yang dihasilkan, serta hanya alasan mengapa tes tersembunyi gagal, bukan inputnya. Tidak memengaruhi peringkat atau rating.
✓ closest_pair([[0, 0], [3, 4], [1, 1]])diharapkan 2 <1 md ✓ closest_pair([[2, 2], [2, 2]])diharapkan 0 <1 md ✓ <1 md✓ <1 md✓ <1 md✓ 9 md✓ <1 md✓ 1 md✓ 2 md⏱ batas waktu terlampaui⏱ batas waktu terlampauiKode
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 Codetidak selesai · 0 dari 11 pengujianrespons dalam 60 dtk · waktu eksekusi <1 md · $0.02 SyntaxError: '[' was never closed (line 69)
✗ closest_pair([[0, 0], [3, 4], [1, 1]])diharapkan 2SyntaxError: '[' was never closed (line 69) — ✗ closest_pair([[2, 2], [2, 2]])diharapkan 0SyntaxError: '[' was never closed (line 69) — ✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError⏱ SyntaxError⏱ SyntaxErrorKode
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)Percobaan kedua
selesai · 11 dari 11 pengujianrespons dalam 6.4 dtk · $0.0031Model melihat berapa banyak tes yang gagal, contoh yang gagal beserta nilai yang diharapkan dan yang dihasilkan, serta hanya alasan mengapa tes tersembunyi gagal, bukan inputnya. Tidak memengaruhi peringkat atau rating.
✓ closest_pair([[0, 0], [3, 4], [1, 1]])diharapkan 2 1 md ✓ closest_pair([[2, 2], [2, 2]])diharapkan 0 2 md ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 1.2 dtk⏱ 1.4 dtkKode
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]
Biaya token: $0.03 · Cara babak dijalankan dan dinilai →