#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;
map<pii, int> vis;
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(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]) <= 4 * r * 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 = 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 time | Memory | Grader output |
|---|
| Fetching results... |