oj.uz

Submission #342338

# Submission time Handle Problem Language Result Execution time Memory
342338 2021-01-01T22:51:52 Z limabeans Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 414 ms 492 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }

const int maxn = 1010;




struct dsu {
    vector<int> par, siz;
    int n;
    int cc;
    void init(int _n) {
        n=_n;
        cc=n;
        par.resize(n);
        siz.resize(n,1);
        iota(par.begin(),par.end(),0);
    }
    int parent(int x) {
        return x==par[x]?x:par[x]=parent(par[x]);
    }
    void join(int u, int v) {
        u = parent(u);
        v = parent(v);
        if (u==v) return;
        if (siz[u]<siz[v]) swap(u,v);
        par[v]=u;
        siz[u]+=siz[v];
        cc--;
    }
};

int n;
ll x[maxn], y[maxn];


double sq(double a) {
    return a*a;
}

double dist(int i, int j) {
    return sqrt(sq(x[i]-x[j]) + sq(y[i]-y[j]));
}

bool test(double r) {
    dsu dsu;
    dsu.init(n);
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if (dist(i,j) <= 2.0*r) {
                dsu.join(i,j);
            }
        }
    }

    return dsu.cc==1;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin>>n;
    for (int i=0; i<n; i++) {
        cin>>x[i]>>y[i];
    }

    double lo = 0;
    double hi = 1e12;
    for (int iter=0; iter<100; iter++) {
        double mid = (lo+hi)/2;
        if (test(mid)) {
            hi = mid;
        } else {
            lo = mid;
        }
    }

    cout<<fixed<<setprecision(15)<<hi<<endl;
    
    
    return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 4 ms 364 KB Output is correct
5 Correct 5 ms 364 KB Output is correct
6 Correct 115 ms 492 KB Output is correct
7 Correct 114 ms 364 KB Output is correct
8 Correct 249 ms 420 KB Output is correct
9 Correct 414 ms 436 KB Output is correct
10 Correct 399 ms 492 KB Output is correct