poj1696 Space Ant 点积，叉积，夹角

//某一赛区题，poj题目链接：http://poj.org/problem?id=1696


//题意：在一个平面内给出N个点，每两点之间没有相同的x或y,
//求从y最小的一点开始，每次都向左移动，能有多少点符合并求出点对应的下标（要求路线不相交）。
//解题思路：第一个点是y最小的点，重点在第二个点要找哪个点,就是x轴正方向夹角最小的点;
//再用点积，叉积和夹角，找出其它的点

//0ms AC 代码如下：

#include<iostream>
#include<cstdio>
#include<math.h>
#define eps 1e-8
struct point {int index;double x,y;}p[52];
bool zero(double x)
{
	return x>0.0 ? x<eps:x>-eps;
}
double xmult(point p1,point p2,point p0)
{
	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double dmult(point p1,point p2,point p0)
{
	return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
}
double distance(point p1,point p2)
{
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double angle(point p1,point p2,point p0)
{
	double a=distance(p1,p0);
	double b=distance(p2,p0);
	double c=distance(p1,p2);
	return (a*a+b*b-c*c)/(2*a*b);
}
int f[52];
point s,e;
int ans[52];
int main()
{
	int cas;
	scanf("%d",&cas);
	while(cas--)
	{
		int n;
		int i,j;
		scanf("%d",&n);
		int miny=1,secend=1;
		for(i=1;i<=n;i++)
		{
			scanf("%d%lf%lf",&p[i].index,&p[i].x,&p[i].y);
			f[i]=0;
		}
		if(n==1)
		{
			printf("1 1\n");
			continue;
		}
		for(i=1;i<=n;i++)
		{
			if(p[miny].y>p[i].y)miny=i;
		}
		double judge=-1;
		for(i=1;i<=n;i++)
		{
			if(i!=miny)
			{
				point t;
				t.x=p[miny].x+100;//
				t.y=p[miny].y;
				double temp=angle(p[i],t,p[miny]);
				if(temp-judge>0.0)
				{secend=i;
				judge=temp;
				}
			}
		}
		s=p[p[miny].index];
		e=p[p[secend].index];
		f[p[miny].index]=1;
		f[p[secend].index]=1;
		ans[0]=p[miny].index;
		ans[1]=p[secend].index;
		int cnt=2;
		for(i=3;i<=n;i++)
		{
			int index=0;
			double xmu=1000000.0;
			double minAng=1.0;
			bool flag=false;
			for(j=1;j<=n;j++)
			{
				if(!f[j])
				{
					double temp=xmult(p[j],s,e);
					double ang=angle(p[j],s,e); 
					double dx=dmult(p[j],s,e);
					if(temp>0.0||temp==0.0&&dx<0.0)
					{
						if(ang-minAng<0.0)
						{
							index=j;
							minAng=ang;
						}
					}
					
				}
			}
			if(index!=ans[cnt-1])
			{
				ans[cnt++]=p[index].index;
				f[p[index].index]=1;
				s=e;
				e=p[index];
				f[index]=1;
			}
		}
		printf("%d",cnt);
		for(i=0;i<cnt;i++)
		{
			printf("% d",ans[i]);
		}
		printf("\n");
		
	}
	return 0;
}