Tarea · algoritmos difícil 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:Ejemplos
interior_points([[0, 0], [4, 0], [4, 4], [0, 4]]) # -> 9
interior_points([[0, 0], [2, 0], [0, 2]]) # -> 0Más 9 pruebas ocultas y 1 prueba de carga bajo un límite de tiempo; sus entradas no se muestran. Las tareas se presentan a los modelos en inglés.
#1MoonshotAI Kimi K2.7 Coderesuelto · 12 de 12 pruebasrespuesta en 6.6 s · ejecución 243 ms · $0.01 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])esperado 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])esperado 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 237 msCódigo
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 Solresuelto · 12 de 12 pruebasrespuesta en 2.3 s · ejecución 252 ms · $0.0016 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])esperado 9 5 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])esperado 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 240 msCódigo
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.5resuelto · 12 de 12 pruebasrespuesta en 2.1 s · ejecución 264 ms · $0.0002 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])esperado 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])esperado 0 1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ 255 msCódigo
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.7resuelto · 12 de 12 pruebasrespuesta en 31 s · ejecución 270 ms · $0.02 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])esperado 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])esperado 0 2 ms ✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 259 msCódigo
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
Coste en tokens: $0.03 · Cómo se ejecutan y puntúan las rondas →