极角排序

Space Ant
题意：
一张图上给出n个点的坐标(xi,yi)，其中xi，yi均为正整数。记这n个点中，拥有最小y的点为A，你开始从点(0, yA)开始走向点A，然后，你可以随意选择径直走去另外的点，但必须满足一下3个条件：
1：只能向左转向。
2：走过的路径为留下一条红色的轨迹。
3：不能越过这条红色的轨迹。
问你最多能到达几个点，并且按到达的顺序输出各个点的标号。
题解：
本题其实就是用极角排序,每次都有一个你的当前点,然后每次都贪心的走以当前点为中心的极角最小的那个点(如果有多个,就走距离当前点最近的那个点即可.)
这样,我们能保证能走过的点数是最多的.

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=60;
const int INF=0x3f3f3f3f3f;
const double EPS=1e-10;
struct Point
{
    double x,y;
    int id;
    Point(double x=0,double y=0):x(x),y(y){}
};
Point p[MAXN],ans[MAXN];
int now;
typedef Point Vector;
Vector operator -(Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
double distance(Vector A)
{
    return A.x*A.x+A.y*A.y;
}
bool cmp(const Point &a,const Point &b)
{
    double res=cross(a-p[now],b-p[now]);//选择离当前点最外层的点
    if(res>0) return true;
    else if(abs(res)<EPS&&distance(a-p[now])<distance(b-p[now])) return true;
    //如果三点共线，选择离当前点近的
    else return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d%lf%lf",&p[i].id,&p[i].x,&p[i].y);
            if(p[i].y<p[0].y) swap(p[0],p[i]);
        }
        now=0;
        sort(p+1,p+n,cmp);//以0为基准找到下一个基准点
        int idx=0;
        ans[idx++]=p[now++];//把0放进去
        for(int i=2;i<n;i++)
        {
            sort(p+i,p+n,cmp);//以now为基准，找到下一个基准点
            ans[idx++]=p[now++];//把now放进去
        }
        ans[idx++]=p[now++];
        printf("%d",idx);
        for(int i=0;i<idx;i++)
        {
            printf(" %d",ans[i].id);
        }
        printf("\n");
    }
    return 0;
}