整数のまま行う偏角ソート
浮動小数点数に直して $\arg$ 求めるの嫌いなので整数のままソートしましょう。 偏角の取りうる範囲は $[0, 2 \pi )$ とします。
追記
投稿直後にもっと賢い方法が投稿され、膝から崩れ落ちました
整数のまま行う偏角ソート（行列式のあれです。）の実装バリエーションの検討とご紹介です。 - ブログ名
追記おわり
ソートする時には、二点 $p = (p _ x, p _ y), q = (q _ x, q _ y)$ が与えられたときにどちらの偏角が大きいのか判定できればOKです。 なので二点の比較を行う方法だけ考えます。
ざっくりと比較
まずは座標平面を三つに切り分けて大まかな位置を特定します。
- 偏角 $[0, \pi / 2]$
- 偏角 $(\pi / 2, \pi]$
- 偏角 $(\pi, 2 \pi)$
これ以外の切り分け方でも大丈夫ですが、座標の正負だけ見ればいいのでこれが一番楽だと思います。 この段階で２点の属する領域が異なれば、それだけで大小関係を決定できます。
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 - フ
Python3 だと全然間に合いませんでした。cmp_to_key の呼び出しが重いっぽい？
Sort Points by Argument (Library Checker)
$\arctan$ って書くとはてなキーワードリンクのせいで $\KaTeX$ 効かないのやめてくれ～～～～