#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
struct dsu{
vector<int> par;
int comp;
dsu(int n){
par.resize(n);
iota(par.begin(),par.end(),0);
comp = n;
}
int getP(int node){
if(node == par[node]) return node;
return par[node] = getP(par[node]);
}
void add(int a,int b){
a = getP(a) , b = getP(b);
if(a == b) return;
par[b] = a;
comp --;
}
};
double dis(pair<int,int> p1 , pair<int,int> p2){
double x1 = p1.first , y1 = p1.second;
double x2 = p2.first , y2 = p2.second;
return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
void solve(){
int n;
cin>>n;
vector<pair<int,int>> v(n);
for(auto &[x,y] : v) cin>>x>>y;
double l = 0;
double r = 1e10;
double ans = 0;
for(int _=0;_<200;_++){
double md = (l + r) / 2;
dsu ds(n);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(dis(v[i],v[j]) > 2*md) continue;
ds.add(i,j);
}
}
if(ds.comp == 1) ans = md , r = md;
else l = md;
}
cout<<fixed<<setprecision(6)<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
Compilation message
odasiljaci.cpp: In function 'void solve()':
odasiljaci.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
33 | for(auto &[x,y] : v) cin>>x>>y;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
3 ms |
452 KB |
Output is correct |
| 5 |
Correct |
4 ms |
348 KB |
Output is correct |
| 6 |
Correct |
86 ms |
348 KB |
Output is correct |
| 7 |
Correct |
86 ms |
600 KB |
Output is correct |
| 8 |
Correct |
179 ms |
348 KB |
Output is correct |
| 9 |
Correct |
309 ms |
472 KB |
Output is correct |
| 10 |
Correct |
311 ms |
344 KB |
Output is correct |
