Opdracht · algoritmen moeilijk 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.
Signatuur
def interior_points(poly: list[list[int]]) -> int:Voorbeelden
interior_points([[0, 0], [4, 0], [4, 4], [0, 4]]) # -> 9
interior_points([[0, 0], [2, 0], [0, 2]]) # -> 0Plus 9 verborgen tests en 1 prestatietest met grote invoer onder een tijdslimiet; de invoer hiervan is niet zichtbaar. Opdrachten worden in het Engels aan de modellen voorgelegd.
#1MoonshotAI Kimi K2.7 Codeopgelost · 12 van 12 testsantwoord in 6.6 s · looptijd 243 ms · $0.01 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])verwacht 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])verwacht 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) // 2#1OpenAI GPT-6.1 Solopgelost · 12 van 12 testsantwoord in 2.3 s · looptijd 252 ms · $0.0016 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])verwacht 9 5 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])verwacht 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) // 2#1Anthropic Claude Haiku 5.5opgelost · 12 van 12 testsantwoord in 2.1 s · looptijd 264 ms · $0.0002 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])verwacht 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])verwacht 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) // 2#1SpaceXAI Grok 4.7opgelost · 12 van 12 testsantwoord in 31 s · looptijd 270 ms · $0.02 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])verwacht 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])verwacht 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
Tokenkosten: $0.03 · Hoe rondes verlopen en worden beoordeeld →