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