Submission #970980

#	Time	Username	Problem	Language	Result	Execution time	Memory
970980		RandomUser	Odašiljači (COCI20_odasiljaci)	C++17	42 / 70	804 ms	444 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;


double dist(pii x, pii y) {
    return sqrt((x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second));
}

struct DSU {
    int n, comp;
    vector<int> par, size;

    void config(int _n) {
        n = _n + 1;
        comp = _n;
        par.resize(n+1);
        size.resize(n+1, 1);
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int get(int u) {
        if(u == par[u]) return u;
        return par[u] = get(par[u]);
    }

    bool uni(int u, int v) {
        u = get(u), v = get(v);

        if(u == v) return false;
        if(size[u] < size[v]) swap(u, v);

        size[u] += size[v];
        par[v] = u;
        comp--;

        return true;
    }

    int getComp() { return comp; }
};

int main() {
    int n;
    cin >> n;

    vector<pii> v(n);
    for(pii &x : v) cin >> x.first >> x.second;

    double l=0.5, r=1e12, ans=1e12;
    while(r - l > 1e-9) {
        double mid = (l + r) / 2;
        DSU dsu; dsu.config(n);

        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i == j) continue;
                if(dist(v[i], v[j]) <= 2 * mid) dsu.uni(i, j);
            }
        }

        if(dsu.getComp() == 1) ans = r = mid;
        else l = mid;
    }

    cout << setprecision(8) << fixed << ans << '\n';
    return 0;
}

• Subtask 1: 42 / 70