Submission #1318075

#TimeUsernameProblemLanguageResultExecution timeMemory
1318075cavid_07Odašiljači (COCI20_odasiljaci)C++20
70 / 70
222 ms9284 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<double> x(n + 1), y(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    double l = 0, r = 1e12, best = -1;
    for (int w = 1; w <= 100; w++) {
        double m = (l + r) / 2.0;
        vector<int> adj[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                double f = abs(x[i] - x[j]);
                double g = abs(y[i] - y[j]);
                if (sqrt(f * f + g * g) <= m * 2) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
        vector<int> vis(n + 1, 0);
        queue<int> q;
        q.push(1);
        while (q.size()) {
            int u = q.front();
            q.pop();
            vis[u] = 1;
            for (int v: adj[u]) {
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
        bool ok = true;
        for (int i = 1; i <= n; i++) {
            if (vis[i] == 0) ok = false;
        }
        if (ok) {
            r = m;
            best = m;
        }
        else {
            l = m;
        }
    }
    cout << setprecision(7) << fixed << best << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...