مسئله · الگوریتم‌ها سخت Python ·
Lattice points inside a polygon
poly lists the vertices of a simple polygon (its edges don't cross or touch except at shared vertices) in order, clockwise or counter-clockwise. Coordinates are integers with absolute value up to 10**9; consecutive vertices are distinct, may be collinear, and the area is positive. Return how many points with integer coordinates lie strictly inside the polygon (not on its boundary). Up to 200,000 vertices.
امضای تابع
def interior_points(poly: list[list[int]]) -> int:نمونه‌ها
interior_points([[0, 0], [4, 0], [4, 4], [0, 4]]) # -> 9
interior_points([[0, 0], [2, 0], [0, 2]]) # -> 0به‌همراه 9 تست مخفی و 1 تست با ورودی بزرگ با محدودیت زمانی؛ ورودی‌های آن‌ها نمایش داده نمی‌شوند. مسئله‌ها به زبان انگلیسی به مدل‌ها داده می‌شوند.
رتبه 1MoonshotAI Kimi K2.7 Codeحل‌شده · 12 از 12 تستپاسخ در 6.6 ثانیه · زمان اجرا 243 میلی‌ثانیه · $0.01 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])مورد انتظار 9 <1 میلی‌ثانیه ✓ interior_points([[0, 0], [2, 0], [0, 2]])مورد انتظار 0 <1 میلی‌ثانیه ✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه⏱ 237 میلیثانیهکد
import math from typing import List def interior_points(poly: List[List[int]]) -> int: n = len(poly) if n < 3: return 0 area2 = 0 boundary = 0 x0, y0 = poly[0] px, py = x0, y0 for i in range(1, n): x, y = poly[i] area2 += px * y - x * py dx = x - px dy = y - py boundary += math.gcd(abs(dx), abs(dy)) px, py = x, y # closing edge area2 += px * y0 - x0 * py boundary += math.gcd(abs(x0 - px), abs(y0 - py)) area2 = abs(area2) # Pick's theorem: A = I + B/2 - 1, A2 = 2*A # I = (A2 - B + 2) / 2 return (area2 - boundary + 2) // 2رتبه 1OpenAI GPT-6.1 Solحل‌شده · 12 از 12 تستپاسخ در 2.3 ثانیه · زمان اجرا 252 میلی‌ثانیه · $0.0016 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])مورد انتظار 9 5 میلی‌ثانیه ✓ interior_points([[0, 0], [2, 0], [0, 2]])مورد انتظار 0 <1 میلی‌ثانیه ✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه⏱ 240 میلیثانیهکد
from math import gcd def interior_points(poly: list[list[int]]) -> int: area2 = 0 boundary = 0 px, py = poly[-1] for x, y in poly: area2 += px * y - x * py boundary += gcd(x - px, y - py) px, py = x, y return (abs(area2) - boundary + 2) // 2رتبه 1Anthropic Claude Haiku 5.5حل‌شده · 12 از 12 تستپاسخ در 2.1 ثانیه · زمان اجرا 264 میلی‌ثانیه · $0.0002 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])مورد انتظار 9 <1 میلی‌ثانیه ✓ interior_points([[0, 0], [2, 0], [0, 2]])مورد انتظار 0 1 میلی‌ثانیه ✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه⏱ 255 میلیثانیهکد
from math import gcd def interior_points(poly: list[list[int]]) -> int: n = len(poly) twice_area = 0 boundary = 0 for i in range(n): x1, y1 = poly[i] x2, y2 = poly[(i + 1) % n] twice_area += x1 * y2 - x2 * y1 boundary += gcd(abs(x2 - x1), abs(y2 - y1)) T = abs(twice_area) return (T - boundary + 2) // 2رتبه 1SpaceXAI Grok 4.7حل‌شده · 12 از 12 تستپاسخ در 31 ثانیه · زمان اجرا 270 میلی‌ثانیه · $0.02 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])مورد انتظار 9 <1 میلی‌ثانیه ✓ interior_points([[0, 0], [2, 0], [0, 2]])مورد انتظار 0 2 میلی‌ثانیه ✓ 1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه⏱ 259 میلیثانیهکد
import math def interior_points(poly: list[list[int]]) -> int: n = len(poly) area2 = 0 b = 0 for i in range(n): x1, y1 = poly[i] x2, y2 = poly[(i + 1) % n] area2 += x1 * y2 - x2 * y1 b += math.gcd(abs(x2 - x1), abs(y2 - y1)) return (abs(area2) - b) // 2 + 1
هزینه توکن‌ها: $0.03 · نحوه برگزاری راندها و امتیازدهی ←