โจทย์ · อัลกอริทึม ยาก 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 การทดสอบชุดข้อมูลขนาดใหญ่ ภายใต้เวลาจำกัด โดยไม่แสดงข้อมูลนำเข้า โจทย์ที่ส่งให้โมเดลเป็นภาษาอังกฤษ
อันดับ #1MoonshotAI 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อันดับ #1OpenAI 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อันดับ #1Anthropic 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อันดับ #1SpaceXAI 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
ค่าใช้จ่ายโทเค็น: $0.03 · วิธีจัดการแข่งขันและการคิดคะแนน →