凸包
(expansion/geometry/convex_hull.py)

• View this file on GitHub
• Last update: 2023-07-16 17:06:17+09:00

概要

凸包を求めます． $[(x_1, y_1), (x_2, y_2), \ldots]$ の形式で頂点を与えてください．

使い方

convex_hull_points = convex_hull(points)

Code

def convex_hull(xy, multi=False):
    xy.sort(key=lambda x: (x[1], x[0]))
    res = []

    def cross3(a, b, c):
        return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

    if multi:

        def f(a, b, c):
            return cross3(a, b, c) > 0

    else:

        def f(a, b, c):
            return cross3(a, b, c) >= 0

    for p in xy:
        while len(res) > 1 and f(res[-1], res[-2], p):
            res.pop()
        res.append(p)

    le = len(res)
    for p in xy[::-1][1:]:
        while len(res) > le and f(res[-1], res[-2], p):
            res.pop()
        res.append(p)
    res.pop()
    return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat
    bundled_code = language.bundle(
                   ^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page