偏角でソート

与えられた点の集合を，偏角（あるいは原点と各点を通る直線の傾き）によってソートすることを考えます．

まず，傾き（y / x）や偏角（atan2）を計算した上でソートすることが考えられます．しかし，この方法では，誤差によって正しくソートできない可能性があります（例：E - 7 (ABC225E - フ - 競プロはじめました)）．

こうした事情から，入力が全て整数の場合，整数だけを用いてソートする方法が欲しくなります．これは，比較関数をベクトルの「外積」で定義すれば実現できます．

比較関数

傾きで考える

原点と点$\boldsymbol{r}_{1} = (x_{1},y_{1})$を通る「直線1」の傾きと，原点と$\boldsymbol{r}_{2} = (x_{2},y_{2})$を通る「直線2」の傾きを比較する．

$x_{1}, x_{2} > 0$のとき，「直線1」の傾きが「直線2」の傾きより大きい条件は

\begin{aligned}
& \frac{y_{1}}{x_{1}} > \frac{y_{2}}{x_{2}} \\
&\Leftrightarrow x_{2} y_{1} - x_{1} y_{2} > 0
\end{aligned}

である．ここで，

\begin{aligned}
f(\boldsymbol{r}_{1}, \boldsymbol{r}_{2})
&=x_{2} y_{1} - x_{1} y_{2}
\end{aligned}

とすれば，$f(\boldsymbol{r}_{1}, \boldsymbol{r}_{2})$は

\begin{aligned}
\begin{cases}
\, > 0 & (\text{「直線1」の傾き > 「直線2」の傾き}) \\
\, = 0 & (\text{「直線1」の傾き = 「直線2」の傾き}) \\
\, < 0 & (\text{「直線1」の傾き < 「直線2」の傾き})
\end{cases}
\end{aligned}

を満たす．

外積で考える

$f$は外積で表せる．外積の正負が2点$\boldsymbol{r}_{1}, \boldsymbol{r}_{2}$の偏角の大小を表しているのは当然である．

\begin{aligned}
f(\boldsymbol{r}_{1}, \boldsymbol{r}_{2})
&=\boldsymbol{r}_{2} \times \boldsymbol{r}_{1} \\
&=
\begin{pmatrix}
x_{2} \\
y_{2}
\end{pmatrix} \times
\begin{pmatrix}
x_{1} \\
y_{1}
\end{pmatrix} \\
&= x_{2} y_{1} - y_{2} x_{1}
\end{aligned}

すべての点の偏角が$[0, \pi)$にある場合はこれを比較関数としてソートできる．

ソート

Python

以下に「cmp パラメータを利用した古い方法」として説明がある．
ソート HOW TO — Python 3.12.1 ドキュメント

from functools import cmp_to_key

def f(r1, r2):
  x1, y1 = r1
  x2, y2 = r2
  return x2 * y1 - y2 * x1

p = [(1, 3), (2, 2), (1, 1)]
p.sort(key = cmp_to_key(f))
print(p)  # [(2, 2), (1, 1), (1, 3)]