제출 #1318041

#제출 시각아이디문제언어결과실행 시간메모리
1318041ezimOdašiljači (COCI20_odasiljaci)C++20
28 / 70
1095 ms656 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; long double sqrtt(long double n) { long double l = 0; long double r = 1e9; long double best = -1; while (r - l >= eps) { long double m = (l + r) / 2; if (m * m >= n) { r = m; best = m; } else { l = m; } } return best; } 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 = sqrtt(d); if (vis[{x[i], y[i]}] == 0 && 1.0 * e / 2 <= r) { 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...