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...