제출 #1321101

#제출 시각아이디문제언어결과실행 시간메모리
1321101saleh_mursudluOdašiljači (COCI20_odasiljaci)C++20
70 / 70
563 ms496 KiB
#include <bits/stdc++.h> using namespace std; const long long MAX = 1005; const long double EPS = 1e-6; long long n; long long vt[MAX]; map<long long, pair<long long, long long>> mp; pair<long long, long long> p[MAX]; long double vs(pair<long long, long long> a, pair<long long, long long> b) { return (long double)(a.first - b.first) * (a.first - b.first) + (long double)(a.second - b.second) * (a.second - b.second); } bool salam(long double r) { queue<pair<long long, long long>> q; q.push(mp[1]); for (long long i = 1; i <= n; i++) vt[i] = 0; vt[1] = 1; while (!q.empty()) { auto u = q.front(); q.pop(); for (long long i = 1; i <= n; i++) { if (!vt[i] && vs(u, mp[i]) <= 4 * r * r) { vt[i] = 1; q.push(mp[i]); } } } for (long long i = 1; i <= n; i++) if (!vt[i]) return false; return true; } void solve() { cin >> n; long long cnt = 1; for (long long i = 1; i <= n; i++) { long long u, v; cin >> u >> v; p[i] = {u, v}; mp[cnt++] = p[i]; } long double l = 0, r = 1e8, m, ans = 0; while (r - l > EPS) { m = (l + r) / 2; if (salam(m)) { ans = m; r = m; } else l = m; } cout << fixed << setprecision(7) << ans; } signed main() { long long z=1; while(z--){ solve(); }}
#Verdict Execution timeMemoryGrader output
Fetching results...