任务 · 算法 困难 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) // 2第 1 名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) // 2第 1 名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) // 2第 1 名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
Token 成本: $0.03 · 轮次运行与评分规则 →