Submission #1318053

#TimeUsernameProblemLanguageResultExecution timeMemory
1318053bshaliOdašiljači (COCI20_odasiljaci)C++20
56 / 70
1096 ms500 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(), x.end() #define inf (int)3e18 #define ff first #define ss second using vi = vector<int>; using vii = vector<pair<int, int>>; using vvi = vector<vector<int>>; using pii = pair<int, int>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MAX = 1005; const long double EPS = 1e-7; int n; map<pii, int> vis; pii a[MAX]; long double dist(pii a, pii b) { return sqrtl((a.ff - b.ff) * (a.ff - b.ff) + (a.ss - b.ss) * (a.ss - b.ss)); } bool check(long double r) { queue<pii> q; q.push(a[1]); for (int i = 1; i <= n; i++) vis[a[i]] = 0; vis[a[1]] = 1; while (q.size()) { auto u = q.front(); q.pop(); for (int i = 1; i <= n; i++) { if (vis[a[i]] == 0 && dist(u, a[i]) <= 2 * r) { vis[a[i]] = 1; q.push(a[i]); } } } for (int i = 1; i <= n; i++) if (vis[a[i]] == 0) return false; return true; } void solve() { cin >> n; for (int i = 1; i <= n; i++) { int u, v; cin >> u >> v; a[i].ff = u, a[i].ss = v; } long double l = 0, r = 1e9 + 5, m = 0, ans = 12; while (r - l > EPS) { m = (l + r) / 2; if (check(m)) { ans = m; r = m; } else { l = m; } } cout << fixed << setprecision(7) << ans; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int tt = 1; // cin >> tt; while (tt--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...