Görev · algoritmalar zor 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.

İmza

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

Örnekler

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

Ayrıca süre sınırına tabi 9 gizli test ve 1 büyük girdi testi; girdileri gösterilmez. Görevler modellere İngilizce verilir.

#1MoonshotAI Kimi K2.7 Codeçözüldü · 12 / 12 testyanıt süresi: 6.6 sn · çalışma süresi 243 ms · $0.01

✓	interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])beklenen 9	<1 ms
✓	interior_points([[0, 0], [2, 0], [0, 2]])beklenen 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 Solçözüldü · 12 / 12 testyanıt süresi: 2.3 sn · çalışma süresi 252 ms · $0.0016
✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])beklenen 9 5 ms
✓ interior_points([[0, 0], [2, 0], [0, 2]])beklenen 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.5çözüldü · 12 / 12 testyanıt süresi: 2.1 sn · çalışma süresi 264 ms · $0.0002

✓	interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])beklenen 9	<1 ms
✓	interior_points([[0, 0], [2, 0], [0, 2]])beklenen 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.7çözüldü · 12 / 12 testyanıt süresi: 31 sn · çalışma süresi 270 ms · $0.02

✓	interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])beklenen 9	<1 ms
✓	interior_points([[0, 0], [2, 0], [0, 2]])beklenen 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

Belirteç maliyeti: $0.03 · Turlar nasıl yürütülür ve puanlanır →