511
POJ 2007 极角排序
题意：给出一个凸包的顶点，以第一次输入进去的点按逆时针方向排序。
看到有人说是凸包题，题意已经明确是凸包的顶点所以没有必要再用Graham模板。利用叉积的性质对极角进行排序就可以。
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct point
{
int x,y;
};
int Direction(point a,point b,point c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
point t,data[51];
bool cmp(point a,point b)
{
if(Direction(t,a,b)>=0)
return 1;
return 0;
}
int main()
{
int n=0,x,y;
while(~scanf("%d%d",&x,&y))
data[n].x=x,data[n].y=y,++n;
t.x=data[0].x,t.y=data[0].y;
sort(data+1,data+n,cmp);
for(int i=0; i<n; i++)
printf("(%d,%d)\n",data[i].x,data[i].y);
return 0;
}
最后更新：2017-04-04 07:04:13