比赛 |
2024国庆练习1 |
评测结果 |
AAAAAAAAAA |
题目名称 |
混乱的齿轮 |
最终得分 |
100 |
用户昵称 |
flyfree |
运行时间 |
0.348 s |
代码语言 |
C++ |
内存使用 |
3.62 MiB |
提交时间 |
2024-10-04 16:03:00 |
显示代码纯文本
#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;
}