課題 · アルゴリズム 上級 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 ms · $0.01 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])期待値 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])期待値 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 237 msコード
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 ms · $0.0016 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])期待値 9 5 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])期待値 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 240 msコード
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 ms · $0.0002 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])期待値 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])期待値 0 1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ 255 msコード
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 ms · $0.02 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])期待値 9 <1 ms ✓ interior_points([[0, 0], [2, 0], [0, 2]])期待値 0 2 ms ✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 259 msコード
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 · 対戦の進行と評価方法について →