记录编号	594767	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 混乱的齿轮	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	0.095 s
提交时间	2024-10-05 08:11:35	内存使用	5.66 MiB

#include <bits/stdc++.h>
using namespace std;

const int N = 3010;

struct ro{
	long long x,y,r;
}roll[N];

int n;
int c[N][N];

int dis(int u,int v){
	long long d=pow((roll[u].x-roll[v].x),2)+pow((roll[u].y-roll[v].y),2);
	long long s=pow((roll[u].r+roll[v].r),2);
	if(s>=d)return 1;
	else return 0;
}

int vis[N],res;

void bfs(int st){
	queue<int> q;
	q.push(st);
	vis[st]++;
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=1;i<=n;i++){
			if(vis[i])continue;
			if(c[u][i]){
				q.push(i);
				vis[i]++;
				res=i;
			}
		}
	}
}

int main(){
	freopen("rollers.in","r",stdin);
	freopen("rollers.out","w",stdout);
	scanf("%d",&n);
	int stt; 
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&roll[i].x,&roll[i].y,&roll[i].r);
		if(roll[i].x==0&&roll[i].y==0)stt=i;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			c[i][j]=dis(i,j);
		}
	}
	bfs(stt);
	printf("%lld %lld",roll[res].x,roll[res].y);
	return 0;
}