原題傳送：http://poj.org/problem?id=1696

　　利用叉積判斷所有點與線段位置關系。下一棵植物A'的位置與螞蟻位置A的連線得到線段AA'，如果所有沒有吃掉的植物均在AA'的左端，那么A'為應該吃的下一目標（如果多個植物在同一條直線上，先吃最近的一個）。因為無論坐標如何變化，在最有的狀態(tài)下，螞蟻總會把所有植物都吃掉，可以利用這個條件退出循環(huán)。

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 }

?

轉載于:https://www.cnblogs.com/huangfeihome/archive/2012/11/03/2752561.html

總結

以上是生活随笔為你收集整理的POJ1696 Space Ant的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。