Scrambled Polygon - POJ 2007(求凸包)

给一些点,这些点都是一个凸包上的顶点,以第一个点为起点顺时针把别的点拍排一下序列。

分析:最简单的极坐标排序了.....................

代码如下:

--------------------------------------------------------------------------------------------------------------------------

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<string>
#include<vector>
#include<math.h>
using namespace std; const double EPS = 1e-;
const double PI = acos(-);
const int MAXN = 1e3+;
int sta[MAXN], top;
int Sign(double t)
{
if(t > EPS)return ;
if(fabs(t) < EPS)return ;
return -;
}
struct point
{
double x, y;
point(double x=, double y=):x(x), y(y){}
point operator - (const point &t)const{
return point(x-t.x, y-t.y);
}
double operator ^(const point &t)const{
return x*t.y - y*t.x;
}
double operator *(const point &t)const{
return x*t.x + y*t.y;
}
}p[MAXN];
double Dist(point a, point b)
{
return sqrt((a-b)*(a-b));
}
bool cmp(point a, point b)
{
int t = Sign((a-p[])^(b-p[])); if(t == )
return Dist(a, p[]) < Dist(b, p[]);
return t > ;
} int main()
{
int i=, N; while(scanf("%lf%lf", &p[i].x, &p[i].y) != EOF)
i++; N = i;
sort(p+, p+N, cmp); for(i=; i<N; i++)
printf("(%.0f,%.0f)\n", p[i].x, p[i].y); return ;
}
上一篇:[LeetCode]题解(python):036-Valid Sudoku


下一篇:Swift之UITabBarController 导航控制器颜色的改变