# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
328548 | nandonathaniel | Odašiljači (COCI20_odasiljaci) | C++14 | 483 ms | 492 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
long double x[MAXN],y[MAXN];
int par[MAXN];
int find(int x){
if(par[x]==x)return x;
return par[x]=find(par[x]);
}
void join(int a,int b){
par[find(a)]=find(b);
}
long double jarak(long double a,long double b,long double c,long double d){
return sqrt((c-a)*(c-a)+(d-b)*(d-b));
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin >> n;
for(int i=1;i<=n;i++){
cin >> x[i] >> y[i];
}
long double ki=0,ka=2e9;
for(int it=1;it<=60;it++){
long double mid=(ki+ka)/2.0;
for(int i=1;i<=n;i++)par[i]=i;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(jarak(x[i],y[i],x[j],y[j])<=2.0*mid){
join(i,j);
}
}
}
int cc=0;
for(int i=1;i<=n;i++){
if(find(i)==i)cc++;
}
if(cc==1){
ka=mid;
}
else ki=mid;
}
cout << fixed << setprecision(9) << ka << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |