Zadanie · algorytmy trudny 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.

Sygnatura

def interior_points(poly: list[list[int]]) -> int:

Przykłady

interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])  # -> 9
interior_points([[0, 0], [2, 0], [0, 2]])  # -> 0

Oraz 9 ukrytych testów i 1 test wydajnościowy z limitem czasu; dane wejściowe nie są widoczne. Zadania są przekazywane modelom w języku angielskim.

#1MoonshotAI Kimi K2.7 Coderozwiązane · 12 z 12 testówodpowiedź w 6.6 s · czas wykonania 243 ms · $0.01

✓	interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])oczekiwano 9	<1 ms
✓	interior_points([[0, 0], [2, 0], [0, 2]])oczekiwano 0	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 237 ms

Kod

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 Solrozwiązane · 12 z 12 testówodpowiedź w 2.3 s · czas wykonania 252 ms · $0.0016
✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])oczekiwano 9 5 ms
✓ interior_points([[0, 0], [2, 0], [0, 2]])oczekiwano 0 <1 ms
✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 240 ms
Kod
```
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.5rozwiązane · 12 z 12 testówodpowiedź w 2.1 s · czas wykonania 264 ms · $0.0002

✓	interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])oczekiwano 9	<1 ms
✓	interior_points([[0, 0], [2, 0], [0, 2]])oczekiwano 0	1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ 255 ms

Kod

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.7rozwiązane · 12 z 12 testówodpowiedź w 31 s · czas wykonania 270 ms · $0.02

✓	interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])oczekiwano 9	<1 ms
✓	interior_points([[0, 0], [2, 0], [0, 2]])oczekiwano 0	2 ms

✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 259 ms

Kod

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

Koszt tokenów: $0.03 · Zasady rund i punktacji →