偏角ソート
(Geometry/atan2_sorted.py)

• View this file on GitHub
• Last update: 2021-05-07 00:33:35+09:00

概要

点の集合を偏角の大きさ (atan2 の大きさ) によってソートする。

使い方

atan2_sorted(points: Iterable[Tuple[int, int]]) -> List[Tuple[int, int]]
$N$ 個の点 points を偏角ソートした結果を返す。点は ($x$ 座標, $y$ 座標) で与える。計算量 $O(N \log N)$

Verified with

• TestCase/LibraryChecker/sort_points_by_argument.test.py

Code

def atan2_sorted(points):
    class Cmp:
        def __init__(self, obj):
            self.obj = obj

        def __lt__(self, other):
            return self.cmp(self.obj, other.obj) < 0

        def cmp(self, p1, p2):
            x1, y1 = p1
            x2, y2 = p2
            if x1 * y2 - y1 * x2 < 0: return 1
            elif x1 * y2 - y1 * x2 > 0: return -1
            else: return 0

    quadrant = [[] for i in range(4)]
    for x, y in points:
        if x == 0 and y == 0: quadrant[2].append((x, y))
        elif x <= 0 and y < 0: quadrant[0].append((x, y))
        elif x > 0 and y <= 0: quadrant[1].append((x, y))
        elif x >= 0 and y > 0: quadrant[2].append((x, y))
        else: quadrant[3].append((x, y))

    res = []
    for i in range(4):
        quadrant[i].sort(key=Cmp)
        for p in quadrant[i]:
            res.append(p)
    return res

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