POJ 1696 Space Ant 極角排序（叉積的應用）

題目大意：給出n個點的編號和坐標，按逆時針方向連接著n個點，按連接的先后順序輸出每個點的編號。

題目思路：Cross（a,b）表示a,b的叉積，若小于0：a在b的逆時針方向，若大于0a在b的順時針方向。每次都sort一下，找出在當前點逆時針方向的最遠的點。數據很小O(N*N*log（N）)的復雜度0s AC了……

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
#define MAX 100005using namespace std;int n,pos,ans[MAX];struct node
{int id,x,y;
}point[MAX];int Dist(int x1,int y1,int x2,int y2)
{return sqrt((x1-x2)*(x1-x2)*1.0 + (y1-y2)*(y1-y2)*1.0);
}int Cross(int x1,int y1,int x2,int y2,int x3,int y3)
{return (x1-x2)*(y1-y3)-(x1-x3)*(y1-y2);
}bool cmp(struct node A,struct node B)
{int op=Cross(point[pos].x,point[pos].y,A.x,A.y,B.x,B.y);if(op>0)return true;else if(op==0 && Dist(point[pos].x,point[pos].y,A.x,A.y)<Dist(point[pos].x,point[pos].y,B.x,B.y))return true;return false;
}int main()
{int T,cnt;scanf("%d",&T);while(T--){pos=0;cnt=0;memset(ans,0,sizeof(ans));scanf("%d",&n);scanf("%d%d%d",&point[0].id,&point[0].x,&point[0].y);for(int i=1;i<n;i++){scanf("%d%d%d",&point[i].id,&point[i].x,&point[i].y);if(point[i].y < point[0].y)//找出起點：左下方的點swap(point[0],point[i]);else if(point[i].y==point[0].y && point[i].x < point[0].x)swap(point[0],point[i]);}sort(point,point+n,cmp);ans[cnt++]=point[pos++].id;for(int i=1;i<n;i++){sort(point+i,point+n,cmp);ans[cnt++]=point[pos++].id;}printf("%d ",cnt);for(int i=0;i<cnt;i++)printf("%d%c",ans[i],i==cnt-1?'\n':' ');}return 0;
}

?