极角排序
极角排序
在平面内取一个定点O,叫极点,引一条射线Ox,叫做极轴,再选定一个长度单位和角度的正方向(通常取逆时针方向)。
对于平面内任何一点M,用ρ表示线段OM的长度(有时也用r表示),θ表示从Ox到OM的角度,ρ叫做点M的极径,θ叫做点M的极角,有序数对 (ρ,θ)就叫点M的极坐标。
那么给定平面上的一些点,把它们按照一个选定的极点排成顺(逆)时针。
代码实现
cmath
库中有一个函数$atan2(y,x)$,返回的值域为$(-\pi,\pi]$。可以直接使用。
tips:可以先计算出极角,再进行排序,可以减少常数
例题
给出n个向量,求夹角最小的两个向量编号。
将n个向量进行极角排序,选相邻的两个计算角度取最小即可。
代码
1 |
|