极角排序用于想按照某个旋转方向来按顺序访问某些点的时候

当然要根据不同的题目要求实现不同的排序

但是有一些通用的技巧，在这里写下吧

先看看这个我实验用的代码（叉积那部分是摘抄的所以有点乱见谅

 

1 #include
     
       2 #define x first 3 #define y second 4 #define N 100005 5 using namespace std; 6 int n; 7 pair
      
       p[N]; 8 bool cmp(pair
       
         A,pair
        
          B){ 9     if(atan2(A.y,A.x)!=atan2(B.y,B.x))10         return atan2(A.y,A.x)
         
           a,pair
          
            b,pair
           
             c)//¼ÆË㼫½Ç19 {20 return cross((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y));21 }22 bool cmp2(pair
            
              a,pair
             
               b) 23 {24 pair
              
                c;//Ô­µã25 c.x = 0;26 c.y = 0;27 if(compare(c,a,b)==0)//¼ÆËã²æ»ý£¬º¯ÊýÔÚÉÏÃæÓнéÉÜ£¬Èç¹û²æ»ýÏàµÈ£¬°´ÕÕX´ÓСµ½´óÅÅÐò28 return a.x
               
                0;30 }31 //*************************32 int main(){33 scanf("%d",&n);34 for(int i=1;i<=n;i++){35 scanf("%lf%lf",&p[i].x,&p[i].y);36 }37 sort(p+1,p+1+n,cmp);//cmp238 cout<<"here you are"<
               
              
             
            
           
          
         
        
       
      
     

 

首先是atan2函数

这个东西要给他点的y，x，注意是先y哦，他会返回一个弧度，排完之后这坨点应该是这个顺序：

第三象限，y轴负半轴，第四象限，原点，x轴正半轴，第一象限，y轴正半轴，第二象限，x轴负半轴

用来排所有点还是很方便很快的，但是缺点是精度丢失，有可能会WA

 

你也可以使用叉乘

叉积天然正负与逆顺有关的特性非常好利用，而且精度也很良好

唯一的问题是如果排的点有两个象限及以上就会非常蛋疼，排的都不知道是啥

上面那个就只能排第二个

第一组点集就算了吧，还会根据读入顺序不同出来的也不同。。。

 

两种方法各有利弊，请酌情选择吧