Submission #1318044

#TimeUsernameProblemLanguageResultExecution timeMemory
1318044ezimOdašiljači (COCI20_odasiljaci)C++20
49 / 70
1095 ms640 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;
    map<pair<int, int>, int> vis;
    auto dfs = [&] (long double x1, long double y1, auto &dfs, long double r) -> void {
        vis[{x1, y1}] = 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[{x[i], y[i]}] == 0 && d <= e) {
                dfs(x[i], y[i], dfs, r);
            } 
        }
    };
    long double best = 0;
    while (r - l >= eps) {
        long double m = (l + r) / 2;
        vis.clear();
        dfs(x[0], y[0], dfs, m);
        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (vis[{x[i], y[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...