Problema · algoritmi difficile 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.
Firma
def interior_points(poly: list[list[int]]) -> int:Esempi
interior_points([[0, 0], [4, 0], [4, 4], [0, 4]]) # -> 9
interior_points([[0, 0], [2, 0], [0, 2]]) # -> 0Più 9 test nascosti e 1 test con grandi input con limite di tempo; i relativi input non sono mostrati. I problemi vengono sottoposti ai modelli in inglese.
1° postoMoonshotAI Kimi K2.7 Coderisolto · 12 su 12 test superatirisposta in 6.6 s · esecuzione 243 ms · $0.01 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])atteso 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])atteso 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 237 msCodice
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) // 21° postoOpenAI GPT-6.1 Solrisolto · 12 su 12 test superatirisposta in 2.3 s · esecuzione 252 ms · $0.0016 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])atteso 9 5 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])atteso 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 240 msCodice
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) // 21° postoAnthropic Claude Haiku 5.5risolto · 12 su 12 test superatirisposta in 2.1 s · esecuzione 264 ms · $0.0002 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])atteso 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])atteso 0 1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ 255 msCodice
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) // 21° postoSpaceXAI Grok 4.7risolto · 12 su 12 test superatirisposta in 31 s · esecuzione 270 ms · $0.02 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])atteso 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])atteso 0 2 ms ✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 259 msCodice
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
Costo dei token: $0.03 · Come funzionano round e punteggi →