极角排序

极角排序

存储

struct point//存储点
{
    double x,y;
};
​
double cross(double x1,double y1,double x2,double y2)　//计算叉积
{
    return (x1*y2-x2*y1);
}
​
double compare(point a,point b,point c)//计算极角
{
    return cross((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y));
}

方法1：利用atan2（）函数按极角从小到大排序。

bool cmp1(point a,point b)
{
    if(atan2(a.y,a.x)!=atan2(b.y,b.x))
        return atan2(a.y,a.x)<atan2(b.y,b.x);
    else return a.x<b.x;
}

方法2：利用叉积按极角从小到大排序。

叉积>0，则向量a在向量b的顺时针方向（粗略的理解为在a在b的下方）；叉积<0，则向量a在向量b的逆时针方向（粗略的理解为在a在b的上方）

bool cmp2(point a,point b) 
{
    point c;//原点
    c.x = 0;
    c.y = 0;
    if(compare(c,a,b)==0)//计算叉积，函数在上面有介绍，如果叉积相等，按照X从小到大排序
        return a.x<b.x;
    else return compare(c,a,b)>0;
}

时间：相较于计算叉积，利用atan2时间快，这个时间会快一点

精度： atan2精度不如叉积高