Submission #854438

#	Time	Username	Problem	Language	Result	Execution time	Memory
854438		vjudge1	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	130 ms	600 KiB

odasiljaci

//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64

struct DSU {
    vector <int> par;
    DSU(int n) {
        par.resize(n);
        iota(par.begin(), par.end(), 0ll);
    }

    inline bool same(int a, int b) {
        return get(a) == get(b);
    }

    inline int get(int a) {
        return par[a] = (par[a] == a ? a : get(par[a]));
    }

    inline bool unite(int a, int b) {
        if(same(a, b)) 
            return false;

        a = get(a), b = get(b);
        par[a] = b;

        return true;
    }
};

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

#define ONLINE_JUDGE
void solve() {
    int n;
    cin >> n;

    pair <int, int> arr[n];
    for(auto &[a, b] : arr) {
        cin >> a >> b;
    }

    auto check = [&](double mid) -> bool {
        DSU dsu(n);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                double dist = sq(arr[i].first - arr[j].first) + sq(arr[i].second - arr[j].second);
                if(dist <= sq(mid)) {
                    dsu.unite(i, j);
                }
            }
        }

        bool ok = true;
        for(int i = 0; i +1 < n; i++) {
            ok &= dsu.get(i) == dsu.get(i +1);
        }

        return ok;
    };

    double l = 0, r = 3e9;
    while(r - l >= 1e-6) {
        double mid = (l + r) / 2;
        if(check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }

    cout << setprecision(9) << l / 2;
    //cerr << l << " " << r << "\n";
    
    return;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

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

    int t = 1; //cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

• Subtask 1: 70 / 70