المهمة · خوارزميات صعب 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 اختبارات مخفية واختبار مدخلات ضخمة واحد ضمن حد زمني؛ لا تُعرض مدخلاتها. تُقدَّم المهام للنماذج باللغة الإنجليزية.
المركز 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 · كيف تُدار الجولات وتُحتسب النقاط ←