cpl/geometry/convex_hull.py

View this file on GitHub
Last update: 1970-01-01 00:00:00+00:00

Code

from cpl.geometry import Polygon, cross


def convex_hull(ps: Polygon) -> Polygon:
    """Andrew's algorithm"""

    def construct(limit, start, stop, step=1):
        for i in range(start, stop, step):
            while len(res) > limit and cross(res[-1] - res[-2], s_ps[i] - res[-1]) < 0:
                res.pop()
            res.append(s_ps[i])

    assert len(ps) >= 3
    s_ps = sorted(ps)
    N = len(s_ps)
    res: Polygon = []
    construct(1, 0, N)
    construct(len(res), N - 2, -1, -1)
    return res[:-1]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.9.2/x64/lib/python3.9/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/opt/hostedtoolcache/Python/3.9.2/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError