1696.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"
#define index ASDFSADF
const double pi=3.14156265359;
struct point
{int x,y;};

point p[51];
int n;
struct vec
{int x,y;};


int set[51];

int cheng(vec t1,vec t2)
{return t1.x*t2.y-t1.y*t2.x;}

double jiao(vec a,vec b)
{return acos((a.x*b.x+a.y*b.y)/sqrt(a.x*a.x+a.y*a.y)/sqrt(b.x*b.x+b.y*b.y));}


int index[51];
void find(int a,vec v)
{int i;vec tt,to;double min=2*pi,f;
int m=-1;
for(i=0;i<n;i++)
if(!set[i]){tt.x=p[i].x-p[a].x;tt.y=p[i].y-p[a].y;
            f=jiao(v,tt);
	 if(f<min){m=i;min=f;to=tt;}
}
if(m==-1)return;
set[m]=1;
cout<<' '<<index[m];
find(m,to);
}


int main()
{int i,j,t,yy,begin;vec v;
	cin>>t;
	while(t--)
	{cin>>n;yy=29999;
	for(i=0;i<n;i++)
	{cin>>index[i]>>p[i].x>>p[i].y;
		if(p[i].y<yy||(p[i].y==yy&&p[i].x<p[begin].x))
		{begin=i;yy=p[i].y;}
	}
	for(i=0;i<n;i++)set[i]=0;
	set[begin]=1;v.x=10;v.y=0;	
	cout<<n<<' '<<index[begin];
	
	find(begin,v);
	cout<<endl;
	
	}
	return 0;
}