偏角ソート
(expansion/geometry/arg_sort.py)

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

概要

与えられた頂点群を偏角ソートします．

使い方

sorted_points = arg_sort(points)

Code

def arg_sort(xy):
    def _area(p):
        if p[0] == 0 and p[1] == 0:
            return 2
        elif p[1] < 0:
            if p[0] < 0:
                return 0
            else:
                return 1
        else:
            if p[0] >= 0:
                return 3
            else:
                return 4

    def merge_sort(xy):
        if len(xy) <= 1:
            return xy
        L = xy[: len(xy) // 2]
        R = xy[len(xy) // 2 :]
        L = merge_sort(L)
        R = merge_sort(R)
        res = []
        lp = 0
        rp = 0
        while lp < len(L) and rp < len(R):
            if _area(L[lp]) < _area(R[rp]):
                res.append(L[lp])
                lp += 1
            elif _area(L[lp]) > _area(R[rp]):
                res.append(R[rp])
                rp += 1
            else:
                if L[lp][1] * R[rp][0] < L[lp][0] * R[rp][1]:
                    res.append(L[lp])
                    lp += 1
                else:
                    res.append(R[rp])
                    rp += 1
        res += L[lp:] + R[rp:]
        return res

    return merge_sort(xy)

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