Submission #1318100

#TimeUsernameProblemLanguageResultExecution timeMemory
1318100bshaliOdašiljači (COCI20_odasiljaci)C++17
70 / 70
534 ms528 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-6; int n; int vis[MAX]; map<int, pii> mp; pii a[MAX]; long double dist(pii a, pii b) { return ((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(mp[1]); for (int i = 1; i <= n; i++) vis[i] = 0; vis[1] = 1; while (q.size()) { auto u = q.front(); q.pop(); for (int i = 1; i <= n; i++) { if (vis[i] == 0 && dist(u, mp[i]) <= 4 * r * r) { vis[i] = 1; q.push(mp[i]); } } } for (int i = 1; i <= n; i++) if (vis[i] == 0) return false; return true; } void solve() { cin >> n; int cnt = 1; for (int i = 1; i <= n; i++) { int u, v; cin >> u >> v; a[i].ff = u, a[i].ss = v; mp[cnt] = a[i]; cnt++; } long double l = 0, r = 1e8, m = 0, ans = 0; while (r - l > EPS) { m = (l + r) / 2; switch (check(m)) { case true: ans = m; r = m; break; case false: l = m; break; } } 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...