Submission #1893600

---

Source Code Expand

from functools import reduce


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


def graham_scan(points):
    points.sort(key=lambda p: (p.real, p.imag))
    lh = reduce(keep_left, points, [])
    uh = reduce(keep_left, reversed(points), [])
    lh.extend(uh[1:-1])
    return lh


def keep_left(hull, r):
    if hull:
        prev = hull.pop()
        while hull:
            p = hull[-1]
            if cross(prev - p, r - p) >= 0:
                hull.append(prev)
                break
            prev = hull.pop()
        else:
            hull.append(prev)
    if not hull or hull[-1] != r:
        hull.append(r)
    return hull


def diameter(convex):
    n = len(convex)
    convex.append(convex[0])
    mi = min(range(n), key=lambda i: convex[i].imag)
    mj = max(range(n), key=lambda i: convex[i].imag)
    md = abs(convex[mi] - convex[mj])
    i, j = mi, mj
    while True:
        if cross(convex[i + 1] - convex[i], convex[j + 1] - convex[j]) >= 0:
            j = (j + 1) % n
        else:
            i = (i + 1) % n
        md = max(md, abs(convex[i] - convex[j]))
        if i == mi and j == mj:
            break
    return md


n = int(input())
points = [complex(*map(int, input().split())) for _ in range(n)]
if n > 2:
    convex = graham_scan(points)
else:
    convex = points
print(diameter(convex))

Submission Info

Judge Result