#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 time | Memory | Grader output |
|---|
| Fetching results... |