整数のまま行う偏角ソート
浮動小数点数に直して $\arg$ 求めるの嫌いなので整数のままソートしましょう。 偏角の取りうる範囲は $[0, 2 \pi )$ とします。
追記
投稿直後にもっと賢い方法が投稿され、膝から崩れ落ちました
ソートする時には、二点 $p = (p _ x, p _ y), q = (q _ x, q _ y)$ が与えられたときにどちらの偏角が大きいのか判定できればOKです。 なので二点の比較を行う方法だけ考えます。
ざっくりと比較
まずは座標平面を三つに切り分けて大まかな位置を特定します。
これ以外の切り分け方でも大丈夫ですが、座標の正負だけ見ればいいのでこれが一番楽だと思います。
この段階で二点の属する領域が異なれば、それだけで大小関係を決定できます。
Python
def area(p: tuple[int, int]): x, y = p if y < 0: return 3 elif x < 0: return 2 else: return 1 def arg_cmp(p: tuple[int, int], q: tuple[int, int]): ap = area(p) aq = area(q) if ap < aq: return -1 elif ap > aq: return 1 else: return 0 # もっと詳しく比較する必要がある
Rust
use std::cmp::Ordering; fn area(p: (i64, i64)) -> u8 { let (x, y) = p; if y < 0 { 3 } else if x < 0 { 2 } else { 1 } } fn arg_cmp(p: &(i64, i64), q: &(i64, i64)) -> Ordering { let ap = area(*p); let aq = area(*q); ap.cmp(&aq) // もっと詳しく比較する必要がある }
細かな比較
座標平面上での三角形の面積の求め方 の考え方を利用すれば、面積の符号によって二点の位置関係を特定できます。 二点の偏角の差が $\pi$ 以上だと符号が反転したり変な感じになってしまうので、そうならないようにあらかじめ三つの領域に分割しました。（かしこい）
Python
def arg_cmp(p: tuple[int, int], q: tuple[int, int]): ap = area(p) aq = area(q) if ap < aq: return -1 elif ap > aq: return 1 else: px, py = p qx, qy = q z = px * qy - py * qx if z > 0: return -1 elif z < 0: return 1 else: return 0
Rust
use std::cmp::Ordering; fn area(p: (i64, i64)) -> u8 { let (x, y) = p; if y < 0 { 3 } else if x < 0 { 2 } else { 1 } } fn arg_cmp(p: &(i64, i64), q: &(i64, i64)) -> Ordering { let ap = area(*p); let aq = area(*q); ap.cmp(&aq).then((q.0 * p.1).cmp(&(p.0 * q.1))) }
あとはこれを sort に渡せば OK です。Python では比較関数を直接渡すことはできないので、 functools の cmp_to_key を使いましょう。
Python
from functools import cmp_to_key points = [(0, 1), (2, -3), (-4, -5), (-6, 7)] points.sort(key=cmp_to_key(arg_cmp))
Rust
fn main() { let mut points: Vec<(i64,i64)> = vec![(0, 1), (2, -3), (-4, -5), (-6, 7)]; points.sort_by(arg_cmp); }
補足
area() を書き換えるだけで偏角の範囲を $[- \pi / 2, \pi / 2)$ に変更したり、点 $(0, 0)$ を必ず先頭に持ってきたりできるのが嬉しいです。
使用例
ABC225E - フ
問題ページ
提出コード (Pypy3)
提出コード (Rust)
Python3 だと全然間に合いませんでした。cmp_to_key の呼び出しが重いっぽい？
