Pythonで誤差なし偏角ソート(第一象限のみ)

math.atan2 でソートしたらWAしたときに。

全ての点が第一象限にあるときのみ使えます。

from functools import cmp_to_key


def arg_sort(p0, p1):
    x0, y0 = p0
    x1, y1 = p1
    if x0 * y1 == x1 * y0:
        return 0
    return 1 if x0 * y1 < x1 * y0 else -1


N = int(input())
lst = []
for _ in range(N):
    x, y = map(int, input().split())
    lst.append((x, y))
lst.sort(key=cmp_to_key(arg_sort))

verify

• https://atcoder.jp/contests/abc225/submissions/26935748
  • 問題の性質上、点 $(x - 1, y)$ の偏角でソートしています。
  • PyPy3 (7.3.0) でAC。 Python だとTLEするかもしれません。

参考文献

• Codeforces Hello 2020 E. New Year and Castle | ARMERIA
  • 上記のコードだとなぜ誤差なくソートできるかが丁寧に解説されています。
  • 第二～第四象限まで点が散らばっている場合に対応したライブラリの作り方も書かれています。この記事で示したコードは全ての点が第一象限にあるときのみ使えることに注意してください。