टास्क · एल्गोरिदम कठिन 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 s · रनटाइम 2.2 s · $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 s⏱ 1.0 s
  कोड

  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 s · रनटाइम 2.6 s · $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 s⏱ 1.3 s
  कोड

  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हल नहीं हुआ · 11 में से 10 टेस्ट्स पासजवाब का समय 5.8 s · रनटाइम 4.3 s · $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⏱ समय सीमा समाप्त (time limit exceeded)⏱ 2.3 s
  कोड

  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)

  दूसरा प्रयास

  हल नहीं हुआ · 11 में से 9 टेस्ट्स पासजवाब का समय 11 s · $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⏱ समय सीमा समाप्त (time limit exceeded)⏱ समय सीमा समाप्त (time limit exceeded)

  कोड

  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हल नहीं हुआ · 11 में से 0 टेस्ट्स पासजवाब का समय 60 s · रनटाइम <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)

  दूसरा प्रयास

  हल किया गया · 11 में से 11 टेस्ट्स पासजवाब का समय 6.4 s · $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 s⏱ 1.4 s

  कोड

  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 · राउंड कैसे आयोजित और स्कोर किए जाते हैं →