POJ1696 Space Ant

　　利用叉积判断所有点与线段位置关系。下一棵植物A'的位置与蚂蚁位置A的连线得到线段AA'，如果所有没有吃掉的植物均在AA'的左端，那么A'为应该吃的下一目标（如果多个植物在同一条直线上，先吃最近的一个）。因为无论坐标如何变化，在最有的状态下，蚂蚁总会把所有植物都吃掉，可以利用这个条件退出循环。

View Code

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <vector>
 5 #define N 55
 6 using namespace std;
 7 
 8 const double eps = 1e-8;
 9 
10 struct node
11 {
12     double x, y;
13 }a[N];
14 
15 bool vis[N];
16 
17 double len(int i, int j)
18 {return sqrt((a[j].y - a[i].y) * (a[j].y - a[i].y) + (a[j].x - a[i].x) * (a[j].x - a[i].x));}
19 
20 int main()
21 {
22     int i, j, t, n, id, aid;
23     double m;
24     vector<int> v;
25     scanf("%d", &t);
26     while(t --)
27     {
28         scanf("%d", &n);
29         v.clear();
30         memset(vis, false, sizeof vis);
31         for(m = 1000.0, i = 1; i <= n; i ++)
32         {
33             scanf("%d%lf%lf", &id, &a[i].x, &a[i].y);
34             if(a[i].y < m)
35             {
36                 m = a[i].y;
37                 aid = id;
38             }
39         }
40         v.push_back(aid);
41         vis[aid] = true;
42         if(n > 1)
43         {
44             while((int)v.size() != n)
45             {
46                 for(aid = -1, i = 1; i <= n; i ++)
47                 {
48                     if(!vis[i])
49                     {
50                         double x1 = a[i].x - a[v[v.size() - 1]].x;
51                         double y1 = a[i].y - a[v[v.size() - 1]].y;
52                         for(j = 1; j <= n; j ++)
53                         {
54                             if(!vis[j] && j != i)
55                             {
56                                 double x2 = a[j].x - a[v[v.size() - 1]].x;
57                                 double y2 = a[j].y - a[v[v.size() - 1]].y;
58                                 if(x1 * y2 - x2 * y1 < 0.0)
59                                     break;
60                             }
61                         }
62                         if(j == n + 1)
63                         {
64                             if(aid == -1 || (len(i, v[v.size() - 1]) < len(aid, v[v.size() - 1])))
65                                 aid = i;
66                         }
67                     }
68                 }
69                 v.push_back(aid);
70                 vis[aid] = true;
71             }
72             printf("%d", n);
73             for(i = 0; i < n; i ++)
74                 printf(" %d", v[i]);
75             putchar('\n');
76         }
77     }
78     return 0;
79 }