# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
376258 | dantoh000 | Odašiljači (COCI20_odasiljaci) | C++14 | 66 ms | 8664 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;
typedef long long ll;
typedef tuple<ll,int,int> iii;
int n;
int x[1005], y[1005];
vector<iii> edg;
int p[1005];
int rk[1005];
int nume = 0;
void init(int n){
for (int i = 0; i < n; i++){
p[i] = i;
rk[i] = 0;
}
}
int find(int x){
return p[x] == x? x : p[x] = find(p[x]);
}
void un(int x, int y){
x = find(x) ,y = find(y);
if (x == y) return;
nume ++;
if (rk[x] < rk[y]) swap(x,y);
p[y] = x;
if (rk[x] == rk[y]) rk[x]++;
}
int main(){
scanf("%d",&n);
for (int i = 0; i < n; i++){
scanf("%d%d",&x[i],&y[i]);
}
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++){
edg.emplace_back((ll)(y[i]-y[j])*(y[i]-y[j]) + (ll)(x[i]-x[j])*(x[i]-x[j]),i,j);
}
}
init(n);
sort(edg.begin(),edg.end());
ll ans = 0;
for (auto e : edg){
ll d;
int x,y;
tie(d,x,y) = e;
ans = d;
un(x,y);
//printf("%lld %d %d\n",d,x,y);
if (nume == n-1) break;
}
printf("%.9Lf\n",pow((long double)ans, 0.5)/2);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |