首页 > 代码库 > 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;}
View Code

 

Scrambled Polygon---poj2007(利用叉积排序)