#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3cSpNGp ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;
struct dsu{
int n,size_;
vector<int> par,siz,color;
dsu(int m){
init(m);
}
void init(int m){
n=m; size_=m;
par.resize(n,0);siz.resize(n,0);color.resize(n,0);
for(int i=0;i<n;i++){
par[i]=i; siz[i]=1;
}
}
void merge(int x,int y,int type=0){
int a=parent(x),b=parent(y);
if(a==b) return;
size_--;
if(siz[a]>siz[b]) {
siz[a]+=siz[b];
par[b]=a;
}else{
siz[b]+=siz[a];
par[a]=b;
}
}
int parent(int x){
return par[x]==x?x:parent(par[x]);
}
bool same(int x, int y){
return parent(x)==parent(y);
}
int size(){
return size_;
}
};
ld qu(ld d){
return d*d;
}
int main(){
_3cSpNGp;
int n;
cin>>n;
vec(pii) a(n);
rep(i,n){
cin>>a[i].fi>>a[i].se;
}
auto f=[&](ld rad)->bool{
dsu uf(n);
rep(i,n){
crep(j,i+1,n){
ld dist=qu(a[i].fi-a[j].fi)+qu(a[i].se-a[j].se);
if(dist<=qu(2*rad)){
uf.merge(i,j);
}
}
}
return uf.size()==1;
};
// cout<<f(1.5)<<"\n";
ld l=0,r=1e9,c=-1;
rep(_,3000){
ld m=(l+r)/2;
if(f(m)){
c=m;
r=m;
}else{
l=m;
}
}
cout<<fixed<<setprecision(10);
cout<<c<<"\n";
//
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
85 ms |
296 KB |
Output isn't correct |
| 2 |
Incorrect |
86 ms |
204 KB |
Output isn't correct |
| 3 |
Incorrect |
102 ms |
292 KB |
Output isn't correct |
| 4 |
Incorrect |
83 ms |
204 KB |
Output isn't correct |
| 5 |
Incorrect |
84 ms |
292 KB |
Output isn't correct |
