Opdracht · algoritmen moeilijk 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.
Signatuur
def closest_pair(points: list[list[int]]) -> int:Voorbeelden
closest_pair([[0, 0], [3, 4], [1, 1]]) # -> 2
closest_pair([[2, 2], [2, 2]]) # -> 0Plus 7 verborgen tests en 2 prestatietests met grote invoer onder een tijdslimiet; de invoer hiervan is niet zichtbaar. Opdrachten worden in het Engels aan de modellen voorgelegd.
#1OpenAI GPT-6 Lunaopgelost · 11 van 11 testsantwoord in 5.7 s · looptijd 2.2 s · $0.0004 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])verwacht 2 11 ms ✓ closest_pair([[2, 2], [2, 2]])verwacht 0 1 ms ✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms⏱ 1.1 s⏱ 1.0 sCode
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 Flashopgelost · 11 van 11 testsantwoord in 4.5 s · looptijd 2.6 s · $0.0027 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])verwacht 2 <1 ms ✓ closest_pair([[2, 2], [2, 2]])verwacht 0 1 ms ✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.3 s⏱ 1.3 sCode
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 Nextniet opgelost · 10 van 11 testsantwoord in 5.8 s · looptijd 4.3 s · $0.0004 ✓ closest_pair([[0, 0], [3, 4], [1, 1]])verwacht 2 2 ms ✓ closest_pair([[2, 2], [2, 2]])verwacht 0 2 ms ✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ <1 ms⏱ tijdslimiet overschreden⏱ 2.3 sCode
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)Tweede poging
niet opgelost · 9 van 11 testsantwoord in 11 s · $0.0004Het model zag hoeveel tests er faalden, de mislukte voorbeelden met de verwachte en geretourneerde waarden, en alleen waarom verborgen tests faalden, niet hun inputs. Telt niet mee voor de eindstand of rating.
✓ closest_pair([[0, 0], [3, 4], [1, 1]])verwacht 2 <1 ms ✓ closest_pair([[2, 2], [2, 2]])verwacht 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ 9 ms✓ <1 ms✓ 1 ms✓ 2 ms⏱ tijdslimiet overschreden⏱ tijdslimiet overschredenCode
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 Codeniet opgelost · 0 van 11 testsantwoord in 60 s · looptijd <1 ms · $0.02 SyntaxError: '[' was never closed (line 69)
✗ closest_pair([[0, 0], [3, 4], [1, 1]])verwacht 2SyntaxError: '[' was never closed (line 69) — ✗ closest_pair([[2, 2], [2, 2]])verwacht 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)Tweede poging
opgelost · 11 van 11 testsantwoord in 6.4 s · $0.0031Het model zag hoeveel tests er faalden, de mislukte voorbeelden met de verwachte en geretourneerde waarden, en alleen waarom verborgen tests faalden, niet hun inputs. Telt niet mee voor de eindstand of rating.
✓ closest_pair([[0, 0], [3, 4], [1, 1]])verwacht 2 1 ms ✓ closest_pair([[2, 2], [2, 2]])verwacht 0 2 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.2 s⏱ 1.4 sCode
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]
Tokenkosten: $0.03 · Hoe rondes verlopen en worden beoordeeld →