首页 > 代码库 > Scrambled Polygon---poj2007(利用叉积排序)
Scrambled Polygon---poj2007(利用叉积排序)
题目链接:http://poj.org/problem?id=2007
题意:乱序给出凸多边形的顶点坐标,要求按逆时 针顺序输出各顶点。给的第一个点一定是 (0,0),没有其他点在坐标轴上,没有三点 共线的情况。
可以运用叉积进行排序,矢量p1×p2 > 0说明p1逆时针旋转<180度可以得到p2;
/*乱序给出凸多边形的顶点坐标,要求按逆时针顺序输出各顶点。给的第一个点一定是(0,0),没有其他点在坐标轴上,没有三点共线的情况。*/#include<stdio.h>#include<algorithm>#include<iostream>using namespace std;typedef long long LL;const int INF = 0x3f3f3f3f;const int N = 110;struct point{ double x, y; point(){} point(double x_, double y_): x(x_), y(y_) {} point friend operator - (const point &p1, const point &p2)///矢量p2p1; { return point(p1.x-p2.x, p1.y-p2.y); } double friend operator ^ (const point &p1, const point &p2) { return p1.x*p2.y - p1.y*p2.x; ///p1×p2: >0说明p1逆时针旋转<180度可得到p2; }};int cmp(point p1, point p2){ if( ((p1-point(0,0)) ^ (p2-point(0,0))) > 0) return 1; return 0;}point a[N];int n;int main(){ n = 0; while(scanf("%lf %lf", &a[n].x, &a[n].y)!=EOF) n++; sort(a+1, a+n, cmp); for(int i=0; i<n; i++) cout<<"("<<a[i].x<<","<<a[i].y<<")"<<endl; return 0;}
Scrambled Polygon---poj2007(利用叉积排序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。