题意:一只蚂蚁,只会向左转,现在给出平面上很多个点,求解一种走法,能使得蚂蚁能经过的点最多,每个顶点该蚂蚁只能经过一次,且所行走的路线不能发生交叉.

对于题目所输入的点,先找出最左下方的顶点(即纵坐标最小的顶点),然后对剩下的顶点按照对与左下点的极角排序,然后反复找最左下的点,反复进行极角排序,同时记录排序后左下的顶点.

极角排序方法:利用叉积,看向量p1和p2的叉积是否小于零,是则说明p1在p2逆时针方向,即p1的极角比p2的大,极角相同则按离p0距离降序排序.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int MAX=55;struct point{    int id;    int x;    int y;}p[MAX],cur;int pnum[MAX];double dis(point a ,point b){    return sqrt(double((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));}int mnt(point p0 ,point p1 ,point p2){    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}bool judgement(point a ,point b){    if(mnt(cur,a,b)>0)        return true;    else if(mnt(cur,a,b)<0)        return false;    else if(dis(cur,a)
          
           >t; while(t--){ cin>>n; for(int i=0 ;i
           
            >p[i].id>>p[i].x>>p[i].y; } sort(p,p+n,cmp); memset(pnum,0,sizeof(pnum)); int cnt=0; cur=p[0]; pnum[cnt++]=p[0].id; for(int i=1 ;i
           
          
         
        
       
      
     

版权声明：本文为博主原创文章，未经博主允许不得转载。