首页 > 代码库 > POJ 1696 - Space Ant

POJ 1696 - Space Ant

2024-08-16 14:00:12   217人阅读

Technorati Tags: POJ,计算几何,凸包

初学计算几何，引入polygon后的第一个挑战——凸包

此题可用凸包算法做，只要把压入凸包的点从原集合中排除即可，最终形成图形为螺旋线。

关于凸包，具体可见凸包五法：http://blog.csdn.net/bone_ace/article/details/46239187

此处简述我O(nH)的Jarvis法(H: 凸包上点数)

技术分享

过程较易于理解。

 

 1 //POJ1696 2 //凸包变形 3 //AC 2016.10.13 4  5 #include "cstdio" 6 #include "cstdlib" 7 #include "iostream" 8 #include "cmath" 9 #define MAXN (55)10 11 struct point{12     int num, x, y;13     bool been;14     point(){}15     point(int X, int Y): x(X), y(Y), been(0){}16     void input(){17         scanf("%d%d%d", &num, &x, &y);18         been = 0;19     }20     friend point operator >> (const point &p1, const point &p2){21         return point(p2.x - p1.x, p2.y - p1.y);22     }23     friend int operator ^ (const point &p1, const point &p2){24         return p1.x * p2.y - p1.y * p2.x;25     }26 }pt[MAXN];27 28 void swap(point &p1, point &p2){29     point p = p1;30     p1 = p2;31     p2 = p;32 }33 34 int main(){35     int m, n;36     freopen("fin.c", "r", stdin);37     scanf("%d", &m);38     while(m--){39         scanf("%d", &n);40         for(int i = 0; i < n; i++){41             pt[i].input();42             for (int j = i; j && (pt[j].y < pt[j - 1].y); j--){43                 swap(pt[j - 1], pt[j]);44             }45         }46         printf("%d %d", n, pt[0].num);47         pt[0].been = 1;48         int cur = 0;49         while (1){50             int tmp = 0;51             for (int i = 0; i < n; i++)52                 if (!pt[i].been){53                     if (!tmp)54                         tmp = i;55                     else if (((pt[cur] >> pt[i]) ^ (pt[cur] >> pt[tmp])) >= 0)56                         tmp = i;57                 }58             if (!tmp) break;59             printf(" %d", pt[tmp].num);60             pt[tmp].been = 1;61             cur = tmp;62         }63         puts("");64     }65 }

 

POJ 1696 - Space Ant


联系
我们