#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<double> x(n + 1), y(n + 1);
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
}
double l = 0, r = 1e12, best = -1;
for (int w = 1; w <= 100; w++) {
double m = (l + r) / 2.0;
vector<int> adj[n + 1];
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
double f = abs(x[i] - x[j]);
double g = abs(y[i] - y[j]);
if (sqrt(f * f + g * g) <= m * 2) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
vector<int> vis(n + 1, 0);
queue<int> q;
q.push(1);
while (q.size()) {
int u = q.front();
q.pop();
vis[u] = 1;
for (int v: adj[u]) {
if (!vis[v]) {
q.push(v);
vis[v] = 1;
}
}
}
bool ok = true;
for (int i = 1; i <= n; i++) {
if (vis[i] == 0) ok = false;
}
if (ok) {
r = m;
best = m;
}
else {
l = m;
}
}
cout << setprecision(7) << fixed << best << '\n';
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |