Submission #1321157

#TimeUsernameProblemLanguageResultExecution timeMemory
1321157b_esma101811Odašiljači (COCI20_odasiljaci)C++20
70 / 70
155 ms9096 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAX = 1e3 + 10; const double INF = 1e18; void solve() { vector<int> vt; int n; cin >> n; double a[n + 1]; double b[n + 1]; for(int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; } if(n == 1) { cout << 0.0000000 << endl; return; } double l = 1, r = 1e9, best = -1, ep = 0.0000001; while(r - l >= ep) { vector<int> adj[n + 5]; vector<int> vis(n + 5, 0); queue<int> q; double m = (l + r) / 2.00; for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { if(sqrt((abs(a[i] - a[j]) / 2) * (abs(a[i] - a[j]) / 2) + (abs(b[i] - b[j]) / 2) * (abs(b[j] - b[i]) / 2)) <= m) { adj[i].push_back(j); adj[j].push_back(i); } } } 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 check = true; for(int i = 1; i <= n; i++) { if(!vis[i]) { check = false; } } if(check) { r = m; best = m; } else { l = m; } } cout << setprecision(7) << fixed << best << endl; } signed main(){ int t = 1; //cin >> t; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...