极角排序理解

这里我们说的极角排序，指的是对于二维坐标中的点，当然也可以说是向量。极角排序的用途一般是预处理二维平面中的点，使之变得相对有序，接下来在有序的条件小用O（n）或者O（nlogn）处理，而不是无序条件下的O（n*n）的枚举。

应用链接  https://www.cnblogs.com/gzr2018/p/10873518.html

极角排序：根据数学知识，在极坐标的情况下，有一个原地，一个参考方向（x轴正方向），现在对于其他点，对于原点，即存在一个极坐标（r，thata），对于极角排序。

关于叉积：叉积=0是指两向量平行（重合）；叉积>0，则向量a在向量b的顺时针方向（粗略的理解为在a在b的下方）；叉积<0，则向量a在向量b的逆时针方向（粗略的理解为在a在b的上方）

如下利用叉积进行极角排序。

1 bool cmp2(point a,point b) 
2 {
3     point c;//原点
4     c.x = 0;
5     c.y = 0;
6     if(compare(c,a,b)==0)//计算叉积，compare函数是计算向量c->a,c->b的叉积，如果叉积相等，按照X从小到大排序
7         return a.x<b.x;
8     else return compare(c,a,b)>0;
9 }

 如下利用atan2函数计算atan2值利用atan2排序。

函数形式：atan2（y，x）。范围是[-pi,pi]，返回值是此点与远点连线与x轴正方向的夹角

由于3，4象限的atan2值为负，可以对他们加上一个2*pi，这样sort之后，象限就是从第一到第四排序好了。

atan2函数值举例如下：

0.785398 :atan2(1,1) 一象限

2.35619 :atan2(1,-1)二象限

-2.35619 :atan2(-1,-1)三象限
-0.785398 :atan2(-1,1)四象限

int cnt=0;
for(int j=0;j<n;j++){
if(i!=j)p[cnt++]=atan2(po[j].y-po[i].y,po[j].x-po[i].x);
if(p[cnt-1]<0)p[cnt-1]+=2*pi;
}
sort(p,p+cnt);
for(int j=0;j<cnt;j++)p[j+cnt]=p[j]+2*pi;//这行代码可选，是为了把前后的向量合起来，如果需要比较向量的相邻关系

 两种方法的比较：用叉积精度更高，但是时间花销大；tan2精度稍微低一些，时间快。记得有个题用叉积排序结果TLE了，当然有些题用tan2可能会WA!!!