POJ1696-凸包

发布时间:2017-6-22 22:18:49 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ1696-凸包",主要涉及到POJ1696-凸包方面的内容,对于POJ1696-凸包感兴趣的同学可以参考一下。

题目:题目链接   题意:找逆时针螺旋线最多能连几个点   分析:贪心使用一些几何上的极角排序,凸包的应用,每次都连最外面的点即可。每次找到一个当前点curp,除了第一 次是对数组按纵坐标排序得出外,剩下的均按极角排序。使用一个ans数组记录链接的每一个点:   代码:   #include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; struct Point { int x, y; int index; }; Point curp; int Cross(const Point &o, const Point &a, const Point &b) { return (a.x - o.x)*(b.y - o.y) - (b.x - o.x)*(a.y - o.y); } bool CmpByy(const Point &a, const Point &b) { return a.y < b.y; } double dis(const Point &a, const Point &b) { return sqrt(double((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y))); } bool CmpBYAngle(const Point &a, const Point &b) { int res = Cross(curp, a, b); if(res > 0) return true; else if(res < 0) return false; else { double dis1 = dis(a, curp); double dis2 = dis(b, curp); if(dis1 < dis2) return true; else return false; } } Point point[55]; int main() { int M; scanf("%d", &M); int n; while(M--) { scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%d%d%d", &point[i].index, &point[i].x, &point[i].y); sort(point, point+n, CmpByy); curp = point[0]; int ans[1000]; mem(ans, 0); int cnt = 0; int pos = 0; ans[pos++] = curp.index; //cout << " " << curp.index ; for(int i = 1; i < n; i++) { sort(point+i,point+n,CmpBYAngle); curp = point[i]; ans[pos++] = curp.index; cnt++; //cout << " " << curp.index; } printf("%d", pos); for(int i = 0; i < pos; ++i) printf(" %d", ans[i]); printf("\n"); } return 0; }      

上一篇:LeetCode 60: Permutation Sequence
下一篇:线性代数:Ax=b的解

相关文章

关键词: POJ1696-凸包

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。