凸包
(Geometry/convexhull.py)

• View this file on GitHub
• Last update: 2021-05-16 16:23:59+09:00

概要

点集合に対する凸包を求めるアルゴリズム。

使い方

convexhull(points: Iterable[Tuple[int, int]]) -> List[Tuple[int, int]]
2次元平面上の $N$ 個の点集合 points に対する凸包を返す。凸包の頂点で最も左にあるものの中で、最も下にある頂点から順に、反時計回りで返す。計算量 $O(N\log N)$

Verified with

• TestCase/AOJ/CGL_4_A.test.py

Code

def convexhull(points):
    def ccw(p0, p1, p2):
        v1 = p1[0] - p0[0], p1[1] - p0[1]
        v2 = p2[0] - p0[0], p2[1] - p0[1]
        crs = v1[0] * v2[1] - v1[1] * v2[0]
        if crs > 0: return 1  # 反時計回り
        if crs < 0: return -1  # 時計回り
        return 0  # 直線上

    ps = sorted(points)
    if len(ps) <= 2:
        return ps

    lower = [ps[0], ps[1]]
    upper = [ps[0], ps[1]]
    for p in ps[2:]:
        while len(lower) >= 2 and ccw(lower[-2], lower[-1], p) < 0:
            lower.pop()
        lower.append(p)
        while len(upper) >= 2 and ccw(upper[-2], upper[-1], p) > 0:
            upper.pop()
        upper.append(p)
    return lower + upper[::-1][1:-1]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/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.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page