Задача · алгоритмы сложная 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

• 1-е местоOpenAI 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))

• 1-е местоGoogle 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)

• 3-е местоQwen3 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))

• 4-е местоMoonshotAI 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 · Как проходят и оцениваются раунды →