不错的一题，需要极角排序，看了别人的代码做的。。。。。。计算几何啊~~~

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5  6 const double er = 1e-8; 7 struct point 8 { 9     int index;10     int x,y;11 }p[100];12 int n;13 int res;14 15 int dis(point a,point b)16 {17     return sqrt(1.0*(a.x - b.x) * (a.x - b.x) + 1.0*(a.y - b.y)*(a.y - b.y));18 }19 20 double outer_product(point a,point b,point c)21 {22     return (b.x - a.x) * (c.y - a.y) - (b.y - a.y)*(c.x-a.x);23 }24 25 bool cmp(point a,point b)26 {27     double temp = outer_product(p[res - 1],a,b);28     if(temp > er) return true;29     temp = temp > 0?temp:(-temp);30     if(temp < er&&dis(a,p[res - 1]) < dis(b,p[res -1]))31         return true;32     return false;33 }34 35 int main()36 {37     int cas;38     scanf("%d",&cas);39     while(cas --)40     {41         scanf("%d",&n);42         for(int i = 0;i < n;i ++)43         {44             scanf("%d%d%d",&p[i].index,&p[i].x,&p[i].y);45             if(p[i].y < p[0].y) std::swap(p[i],p[0]);46             if(p[i].y == p[0].y)47             {48                 if(p[i].x 
          
           < n;res ++)55         {56             std::sort(p+res,p+n,cmp);57             printf(" %d",p[res].index);58         }59         printf("\n");60     }61 62     return 0;63 }