与えられた点の集合を，偏角（あるいは原点と各点を通る直線の傾き）によってソートすることを考えます．
まず，傾き（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}
である．ここで，& \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})$はf(\boldsymbol{r}_{1}, \boldsymbol{r}_{2})
&=x_{2} y_{1} - x_{1} y_{2}
\end{aligned}
\begin{aligned}
\begin{cases}
\, > 0 & (\text{「直線1」の傾き > 「直線2」の傾き}) \\
\, = 0 & (\text{「直線1」の傾き = 「直線2」の傾き}) \\
\, < 0 & (\text{「直線1」の傾き < 「直線2」の傾き})
\end{cases}
\end{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}
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)]
