Submission #342338

#	Time	Username	Problem	Language	Result	Execution time	Memory
342338		limabeans	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	414 ms	492 KiB

odasiljaci

#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 / 70