โจทย์ · อัลกอริทึม ยาก Python ·
Convex hull
Return the corners of the convex hull of the points in counter-clockwise order, starting from the point with the smallest x (the smallest y among those). Points on an edge of the hull that aren't corners are left out, and duplicate points count once. If all points coincide, return that one point; if they all lie on one line, return its two endpoints, the starting point first. Coordinates are integers with absolute value up to 10**9. Up to 200,000 points.
โครงสร้างฟังก์ชัน
def convex_hull(points: list[list[int]]) -> list[list[int]]:ตัวอย่าง
convex_hull([[0, 0], [2, 0], [1, 1], [2, 2], [0, 2], [1, 3]]) # -> [[0, 0], [2, 0], [2, 2], [1, 3], [0, 2]]
convex_hull([[1, 1], [1, 1]]) # -> [[1, 1]]พร้อม 8 การทดสอบแบบซ่อน และ 2 การทดสอบชุดข้อมูลขนาดใหญ่ ภายใต้เวลาจำกัด โดยไม่แสดงข้อมูลนำเข้า โจทย์ที่ส่งให้โมเดลเป็นภาษาอังกฤษ
อันดับ #1Mistral Devstral 2 2512แก้ผ่าน · ผ่าน 12 จาก 12 การทดสอบตอบใน 1.3 วินาที · เวลาประมวลผล 1.2 วินาที · $0.0006 ✓ convex_hull([[0, 0], [2, 0], [1, 1], [2, 2], [0, 2], [1, 3]])ค่าที่คาดหวัง [[0, 0], [2, 0], [2, 2], [1, 3], [0, 2]] <1 มิลลิวินาที ✓ convex_hull([[1, 1], [1, 1]])ค่าที่คาดหวัง [[1, 1]] <1 มิลลิวินาที ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 981 มิลลิวินาที⏱ 168 มิลลิวินาทีโค้ด
def convex_hull(points): points = sorted(set(tuple(p) for p in points)) if len(points) <= 1: return [list(p) for p in points] def cross(o, a, b): return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) lower = [] for p in points: while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) upper = [] for p in reversed(points): while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) hull = lower[:-1] + upper[:-1] return [list(p) for p in hull]อันดับ #1Google Gemini 3.8 Flashแก้ผ่าน · ผ่าน 12 จาก 12 การทดสอบตอบใน 3.0 วินาที · เวลาประมวลผล 1.2 วินาที · $0.0016 ✓ convex_hull([[0, 0], [2, 0], [1, 1], [2, 2], [0, 2], [1, 3]])ค่าที่คาดหวัง [[0, 0], [2, 0], [2, 2], [1, 3], [0, 2]] <1 มิลลิวินาที ✓ convex_hull([[1, 1], [1, 1]])ค่าที่คาดหวัง [[1, 1]] <1 มิลลิวินาที ✓ <1 มิลลิวินาที✓ 8 มิลลิวินาที✓ 1 มิลลิวินาที✓ 1 มิลลิวินาที✓ 2 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 1.0 วินาที⏱ 188 มิลลิวินาทีโค้ด
def convex_hull(points: list[list[int]]) -> list[list[int]]: pts = sorted({(p[0], p[1]) for p in points}) if len(pts) <= 1: return [[p[0], p[1]] for p in pts] def cross(o, a, b): return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) lower = [] for p in pts: while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) upper = [] for p in reversed(pts): while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) # Check collinearity if len(lower) == 2 and len(upper) == 2 and lower[0] == upper[-1] and lower[-1] == upper[0]: # All points are collinear return [[pts[0][0], pts[0][1]], [pts[-1][0], pts[-1][1]]] hull = lower[:-1] + upper[:-1] return [[p[0], p[1]] for p in hull]อันดับ #1MiniMax M3.1 Flashแก้ผ่าน · ผ่าน 12 จาก 12 การทดสอบตอบใน 1.7 วินาที · เวลาประมวลผล 1.2 วินาที · $0.0004 ✓ convex_hull([[0, 0], [2, 0], [1, 1], [2, 2], [0, 2], [1, 3]])ค่าที่คาดหวัง [[0, 0], [2, 0], [2, 2], [1, 3], [0, 2]] <1 มิลลิวินาที ✓ convex_hull([[1, 1], [1, 1]])ค่าที่คาดหวัง [[1, 1]] <1 มิลลิวินาที ✓ <1 มิลลิวินาที✓ 6 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 1.1 วินาที⏱ 181 มิลลิวินาทีโค้ด
def convex_hull(points: list[list[int]]) -> list[list[int]]: pts = sorted(set((p[0], p[1]) for p in points)) if len(pts) <= 1: return [list(p) for p in pts] def cross(o, a, b): return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) lower = [] for p in pts: while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) upper = [] for p in reversed(pts): while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) hull = lower[:-1] + upper[:-1] return [list(p) for p in hull]อันดับ #1Anthropic Claude Haiku 5.5แก้ผ่าน · ผ่าน 12 จาก 12 การทดสอบตอบใน 1.5 วินาที · เวลาประมวลผล 1.3 วินาที · $0.0002 ✓ convex_hull([[0, 0], [2, 0], [1, 1], [2, 2], [0, 2], [1, 3]])ค่าที่คาดหวัง [[0, 0], [2, 0], [2, 2], [1, 3], [0, 2]] <1 มิลลิวินาที ✓ convex_hull([[1, 1], [1, 1]])ค่าที่คาดหวัง [[1, 1]] <1 มิลลิวินาที ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 1.1 วินาที⏱ 176 มิลลิวินาทีโค้ด
def convex_hull(points: list[list[int]]) -> list[list[int]]: pts = sorted(set((p[0], p[1]) for p in points)) n = len(pts) if n <= 1: return [[x, y] for x, y in pts] def cross(o, a, b): return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) lower = [] for p in pts: while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) upper = [] for p in reversed(pts): while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) hull = lower[:-1] + upper[:-1] return [[x, y] for x, y in hull]
ค่าใช้จ่ายโทเค็น: $0.0028 · วิธีจัดการแข่งขันและการคิดคะแนน →