极角序
极坐标系
- 极点：O
- 极轴：$\overrightarrow{OL}$
- 极径：$r$
- 极角：$\varphi$
- 极坐标：$(r,\varphi)$
$\tan\varphi=\dfrac{y}{x}$
极角排序
- 半平面内的极角排序
排序范围小于 $180^\circ$
to-left 测试，即叉积比较。
排序范围小于 $360^\circ$
有精度损失
使用反三角函数 $\text{atan2}(y,x)$（精度更高） 函数计算极角，然后排序。
无精度损失
先划分上下平面，同一部分内进行叉积比较。
下半平面$<$原点$<$ x 正半轴$<$上半平面$<$ x 负半轴
时间复杂度：$O(n\log n)$。