首页 > 代码库 > POJ 2007 Scrambled Polygon(简单极角排序)
POJ 2007 Scrambled Polygon(简单极角排序)
水题,根本不用凸包,就是一简单的极角排序。
叉乘<0,逆时针。
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std; const int maxn=55; struct point { double x,y; } p[maxn]; double cross(point c1,point b1,point a2) { return (b1.x-c1.x)*(a2.y-c1.y)-(b1.y-c1.y)*(a2.x-c1.x); } bool cmp(point a,point b) { point c; c.x=0;c.y=0; return cross(c,b,a)<0; } int main() { int n=0; while(scanf("%lf %lf",&p[n].x,&p[n].y)!=EOF) n++; sort(p+1,p+n, cmp); for(int i =0; i<n; i++) cout<<"("<<p[i].x<<","<<p[i].y<<")"<<endl; return 0; }
POJ 2007 Scrambled Polygon(简单极角排序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。