记录编号	594723	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 混乱的齿轮	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	0.344 s
提交时间	2024-10-04 18:04:34	内存使用	3.55 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define MAXN 1210
#define mod 0.00001
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll dis[MAXN];
struct node{
	db x,y,r;
}pnt[MAXN];
struct node_qs{
	ll id;
	bool operator <(const node_qs &a)const{
		return dis[id]>dis[a.id];
	}
};
priority_queue<node_qs> q;
ll n,fnt,used[MAXN];
//ll x[MAXN],y[MAXN],r[MAXN];
db kf(db len){
	db l=0.00000,r=20000.00000;
	while(r-l>=mod){
		db mid=(l+r)/2;
		if(mid*mid>=len)r=mid;
		else l=mid;
	}
	return l;
}
int main(){
	freopen("rollers.in","r",stdin);
	freopen("rollers.out","w",stdout);
	memset(dis,0x3f,sizeof(dis));
	n=read();
	for(int i=1;i<=n;i++){
		cin>>pnt[i].x>>pnt[i].y>>pnt[i].r;
		if(pnt[i].x==pnt[i].y&&pnt[i].x==0){
			q.push((node_qs){i});
//			used[i]=1;
			dis[i]=0;
		}
	}
	while(!q.empty()){
		fnt=q.top().id;
		q.pop();
		if(used[fnt])continue;
		used[fnt]=1;
		for(int i=1;i<=n;i++){
			if(used[i]||i==fnt)continue;
			db x=(pnt[i].x-pnt[fnt].x),y=(pnt[i].y-pnt[fnt].y);
//			cout<<x<<" "<<y<<" "<<kf((x*x+y*y))<<endl;
			if(kf((x*x+y*y))<=pnt[i].r+pnt[fnt].r){
				dis[i]=min(dis[i],dis[fnt]+1);
//				q.push(i);
				q.push((node_qs){i});
			}
		}	
	}
	for(int i=1;i<=n;i++){
		if(dis[i]>dis[fnt])fnt=i;
	}
	cout<<pnt[fnt].x<<" "<<pnt[fnt].y;
	return 0;
}