Submission #1318113

#TimeUsernameProblemLanguageResultExecution timeMemory
1318113ezimOdašiljači (COCI20_odasiljaci)C++20
70 / 70
122 ms520 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 1e6, mod = 1e9 + 7, inf = 1e18;
double eps = 0.0000000001;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long double> x(n);
    vector<long double> y(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    long double l = 0;
    long double r = 1e15;
    vector<int> vis(n + 1, 0), viss(n + 1, 0);
    auto dfs = [&] (long double x1, long double y1, auto &dfs, long double r, int j) -> void {
        vis[j] = 1;
        for (int i = 0; i < n; i++) {
            long double d = abs(x1 - x[i]) * abs(x1 - x[i]) + abs(y1 - y[i]) * abs(y1 - y[i]);
            long double e = r * r * 4;
            if (vis[i] == 0 && d <= e) {
                dfs(x[i], y[i], dfs, r, i);
            }
        }
    };
    long double best = 0;
    while (r - l >= eps) {
        long double m = (l + r) / 2;
        vis = viss;
        dfs(x[0], y[0], dfs, m, 0);
        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (vis[i] == 0) {
                ok = false;
            }
        }
        if (ok) {
            r = m;
            best = r;
        }
        else {
            l = m;
        }
    }
    cout << setprecision(7) << fixed << best << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...