POJ 1696 Space Ant

极角排序

每次选择一个最外围的没选过的点，选择的时候需要利用极角排序进行选择

#include<cstdio>

#include<cstring>

#include<vector>

#include<cmath>

#include<queue>

#include<list>

#include<algorithm>

using namespace std;

const double eps=1e-;

struct point

{

    int x,y;

    double alpha;

    int len2;

    int id;

} p[];

int T,n;

vector<point>v;

vector<int>ans;

bool flag[];

bool cmp(const point &a, const point &b)

{

    if(fabs(a.alpha-b.alpha)<eps) return a.len2<b.len2;

    return a.alpha<b.alpha;

}

int len2(point a,point b)

{

    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

}

double f(point a,point b,point c) //返回点a所对应的角的弧度

{

    double B2=(double)len2(a,c);

    double C2=(double)len2(a,b);

    double A2=(double)len2(b,c);

    double COSA=(B2+C2-A2)/(*sqrt(B2)*sqrt(C2));

    return 3.1415926-acos(COSA);

}

int main()

{

    scanf("%d",&T);

    int Miny=;

    while(T--)

    {

        scanf("%d",&n);

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

        {

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

            Miny=min(Miny,p[i].y);

        }

        memset(flag,,sizeof flag);

        ans.clear();

        point pre;pre.x=-;pre.y=Miny;

        point now;now.x=;now.y=Miny;

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

        {

            v.clear();

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

            {

                if(!flag[p[k].id])

                {

                    p[k].alpha=f(now,p[k],pre);

                    p[k].len2=len2(p[k],now);

                    v.push_back(p[k]);

                }

            }

            sort(v.begin(),v.end(),cmp);

            flag[v[].id]=;

            ans.push_back(v[].id);

            pre.x=now.x;

            pre.y=now.y;

            now.x=v[].x;

            now.y=v[].y;

        }

        printf("%d ",ans.size());

        for(int i=; i<ans.size(); i++)

        {

            printf("%d",ans[i]);

            if(i<ans.size()-) printf(" ");

            else printf("\n");

        }

    }

    return ;

}