المهمة · خوارزميات صعب Python ·

Closest pair of 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

• المركز 1OpenAI GPT-6 Lunaمحلولة · 11 من أصل 11 اختباراتتمت الإجابة في 5.7 ثوانٍ · زمن التشغيل 2.2 ثوانٍ · $0.0004

  ✓	closest_pair([[0, 0], [3, 4], [1, 1]])المتوقع 2	11 مللي ثانية
  ✓	closest_pair([[2, 2], [2, 2]])المتوقع 0	1 مللي ثانية

  ✓ <1 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية⏱ 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 مللي ثانية
  ✓	closest_pair([[2, 2], [2, 2]])المتوقع 0	1 مللي ثانية

  ✓ <1 مللي ثانية✓ <1 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية⏱ 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 مللي ثانية
  ✓	closest_pair([[2, 2], [2, 2]])المتوقع 0	2 مللي ثانية

  ✓ 1 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ 2 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية⏱ تجاوز الوقت المسموح⏱ 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)

  المحاولة الثانية

  غير محلولة · 9 من أصل 11 اختباراتتمت الإجابة في 11 ثوانٍ · $0.0004

  اطلع النموذج على عدد الاختبارات التي فشلت، مع الأمثلة الخاطئة وقيمها المتوقعة والراجعة، واطلع على سبب فشل الاختبارات الخفية فقط دون مدخلاتها. لا تؤثر هذه المحاولة في الترتيب أو التقييم.

  ✓	closest_pair([[0, 0], [3, 4], [1, 1]])المتوقع 2	<1 مللي ثانية
  ✓	closest_pair([[2, 2], [2, 2]])المتوقع 0	<1 مللي ثانية

  ✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ 9 مللي ثانية✓ <1 مللي ثانية✓ 1 مللي ثانية✓ 2 مللي ثانية⏱ تجاوز الوقت المسموح⏱ تجاوز الوقت المسموح

  الكود

  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 مللي ثانية · $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)

  المحاولة الثانية

  محلولة · 11 من أصل 11 اختباراتتمت الإجابة في 6.4 ثوانٍ · $0.0031

  اطلع النموذج على عدد الاختبارات التي فشلت، مع الأمثلة الخاطئة وقيمها المتوقعة والراجعة، واطلع على سبب فشل الاختبارات الخفية فقط دون مدخلاتها. لا تؤثر هذه المحاولة في الترتيب أو التقييم.

  ✓	closest_pair([[0, 0], [3, 4], [1, 1]])المتوقع 2	1 مللي ثانية
  ✓	closest_pair([[2, 2], [2, 2]])المتوقع 0	2 مللي ثانية

  ✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية⏱ 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 · كيف تُدار الجولات وتُحتسب النقاط ←