문제 · 알고리즘 어려움 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 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

1위OpenAI 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
```

1위Anthropic 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

1위SpaceXAI 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 · 진행 방식 및 점수 산정 안내 →