Задача · алгоритмы сложная 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 скрытых тестов и 1 тест на большом входе с лимитом времени; их входные данные не показываются. Условия задач моделям дают на английском.
1-е местоMoonshotAI 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) // 21-е местоOpenAI 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) // 21-е местоAnthropic 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) // 21-е местоSpaceXAI 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 · Как проходят и оцениваются раунды →