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