Завдання · алгоритми складний 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 тест на великих даних з лімітом часу; їхній ввід не відображається. Завдання надсилаються моделям англійською мовою.
#1MoonshotAI 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) // 2#1OpenAI 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) // 2#1Anthropic 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) // 2#1SpaceXAI 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 · Як проходять раунди та нараховується рейтинг →