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 100005

using 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>)

        return true;

    else if(op== && 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=;

        cnt=;

        memset(ans,,sizeof(ans));

        scanf("%d",&n);

        scanf("%d%d%d",&point[].id,&point[].x,&point[].y);

        for(int i=;i<n;i++)

        {

            scanf("%d%d%d",&point[i].id,&point[i].x,&point[i].y);

            if(point[i].y < point[].y)//找出起点：左下方的点

                swap(point[],point[i]);

            else if(point[i].y==point[].y && point[i].x < point[].x)

                swap(point[],point[i]);

        }

        sort(point,point+n,cmp);

        ans[cnt++]=point[pos++].id;

        for(int i=;i<n;i++)

        {

            sort(point+i,point+n,cmp);

            ans[cnt++]=point[pos++].id;

        }

        printf("%d ",cnt);

        for(int i=;i<cnt;i++)

            printf("%d%c",ans[i],i==cnt-?'\n':' ');

    }

    return ;

}