比赛 2024国庆练习1 评测结果 AAWAWWWAAA
题目名称 混乱的齿轮 最终得分 60
用户昵称 wdsjl 运行时间 0.098 s
代码语言 C++ 内存使用 5.60 MiB
提交时间 2024-10-04 16:03:00
显示代码纯文本
#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);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&roll[i].x,&roll[i].y,&roll[i].r);
	}
	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(1);
	printf("%lld %lld",roll[res].x,roll[res].y);
	return 0;
}