مسئله · الگوریتم‌ها سخت 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 · نحوه برگزاری راندها و امتیازدهی ←