Tugas · algoritma sulit 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.
Tanda tangan
def interior_points(poly: list[list[int]]) -> int:Contoh
interior_points([[0, 0], [4, 0], [4, 4], [0, 4]]) # -> 9
interior_points([[0, 0], [2, 0], [0, 2]]) # -> 0Ditambah 9 pengujian tersembunyi dan 1 pengujian input besar dengan batas waktu; inputnya tidak ditampilkan. Tugas diberikan kepada model dalam bahasa Inggris.
#1MoonshotAI Kimi K2.7 Codeselesai · 12 dari 12 pengujianrespons dalam 6.6 dtk · waktu eksekusi 243 md · $0.01 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])diharapkan 9 <1 md ✓ interior_points([[0, 0], [2, 0], [0, 2]])diharapkan 0 <1 md ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 237 mdKode
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 Solselesai · 12 dari 12 pengujianrespons dalam 2.3 dtk · waktu eksekusi 252 md · $0.0016 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])diharapkan 9 5 md ✓ interior_points([[0, 0], [2, 0], [0, 2]])diharapkan 0 <1 md ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ 1 md✓ <1 md✓ <1 md✓ <1 md⏱ 240 mdKode
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.5selesai · 12 dari 12 pengujianrespons dalam 2.1 dtk · waktu eksekusi 264 md · $0.0002 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])diharapkan 9 <1 md ✓ interior_points([[0, 0], [2, 0], [0, 2]])diharapkan 0 1 md ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ 1 md⏱ 255 mdKode
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.7selesai · 12 dari 12 pengujianrespons dalam 31 dtk · waktu eksekusi 270 md · $0.02 ✓ interior_points([[0, 0], [4, 0], [4, 4], [0, 4]])diharapkan 9 <1 md ✓ interior_points([[0, 0], [2, 0], [0, 2]])diharapkan 0 2 md ✓ 1 md✓ <1 md✓ 1 md✓ 1 md✓ <1 md✓ 1 md✓ <1 md✓ <1 md✓ <1 md⏱ 259 mdKode
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
Biaya token: $0.03 · Cara babak dijalankan dan dinilai →