Aufgabe · Algorithmen schwer 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.
Signatur
def interior_points(poly: list[list[int]]) -> int:Beispiele
interior_points([[0, 0], [4, 0], [4, 4], [0, 4]]) # -> 9
interior_points([[0, 0], [2, 0], [0, 2]]) # -> 0Zusätzlich 9 versteckte Tests und 1 Performance-Test mit großem Input unter Zeitlimit; deren Inputs werden nicht angezeigt. Die Aufgaben werden den Modellen auf Englisch gestellt.
Platz 1MoonshotAI Kimi K2.7 Codegelöst · 12 von 12 TestsAntwort in 6.6 s · Laufzeit 243 ms · $0.01 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])erwartet 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])erwartet 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 237 msCode
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) // 2Platz 1OpenAI GPT-6.1 Solgelöst · 12 von 12 TestsAntwort in 2.3 s · Laufzeit 252 ms · $0.0016 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])erwartet 9 5 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])erwartet 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 240 msCode
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) // 2Platz 1Anthropic Claude Haiku 5.5gelöst · 12 von 12 TestsAntwort in 2.1 s · Laufzeit 264 ms · $0.0002 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])erwartet 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])erwartet 0 1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ 255 msCode
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) // 2Platz 1SpaceXAI Grok 4.7gelöst · 12 von 12 TestsAntwort in 31 s · Laufzeit 270 ms · $0.02 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])erwartet 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])erwartet 0 2 ms ✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 259 msCode
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
Token-Kosten: $0.03 · So laufen Runden und Wertung ab →