记录编号	175413	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 混乱的齿轮	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2015-08-05 19:12:38	内存使用	1.65 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<cstring>
using namespace std;
struct dd
{
	int x,y,r;
}jie[1160];
struct dr
{
	int zhong;
	int next;
}jiege[4500];
int tot;
int id,fg;
int n,begin,end,head[1160];
bool v[1160],b[1160][1160];
void add(int x,int y)
{
	tot++;
	jiege[tot].zhong=y;
	jiege[tot].next=head[x];
	head[x]=tot;
}
int spfa(int y)
{
	v[y]=1;
	queue<int>q;
	q.push(y);
	int yu;
	while(!q.empty())
	{   
		yu=q.front();
		q.pop();
		for(int i=head[yu];i;i=jiege[i].next)
		{   int jk=jiege[i].zhong;
			if(!v[jk])
			{   v[jk]=1;
			    //cout<<jk<<endl;
				q.push(jk);
			}
		}
	/*	for(int i=1;i<=n;++i)
		{   if(i==yu) continue;
			if(b[i][yu]&&!v[i]){
				v[i]=1;
				//cout<<i<<endl;
				q.push(i);
			}
		}*/
		
	}
   return yu;
}
int main()
{  freopen("rollers.in","r",stdin);
    freopen("rollers.out","w",stdout);
    scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d%d",&jie[i].x,&jie[i].y,&jie[i].r);
		if(jie[i].x==0&&jie[i].y==0)
		   fg=i;
	}
	for(int i=1;i<=n;++i)
	 for(int j=1;j<=i;++j)
	 { if(i==j) continue;
      if((jie[i].x-jie[j].x)*(jie[i].x-jie[j].x)+(jie[i].y-jie[j].y)*(jie[i].y-jie[j].y)==(jie[j].r+jie[i].r)*(jie[i].r+jie[j].r))
           {
              //b[i][j]=b[j][i]=1;
              //cout<<i<<" "<<j<<endl;
              add(i,j);
              add(j,i);
		   }
     }
	int hj=spfa(fg);
	printf("%d %d",jie[hj].x,jie[hj].y);
	return 0;
}