#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> x(n), y(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}
if (n == 1) {
cout << "0.0000000000" << endl;
return 0;
}
double left = 0, right = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double dx = x[i] - x[j];
double dy = y[i] - y[j];
double dist = sqrt(dx*dx + dy*dy);
if (dist > right) right = dist;
}
}
for (int iter = 0; iter < 60; iter++) {
double mid = (left + right) / 2;
vector<bool> visited(n, false);
queue<int> q;
q.push(0);
visited[0] = true;
int count = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < n; v++) {
if (!visited[v]) {
double dx = x[u] - x[v];
double dy = y[u] - y[v];
double dist = sqrt(dx*dx + dy*dy);
if (dist <= 2 * mid) {
visited[v] = true;
q.push(v);
count++;
}
}
}
}
if (count == n) {
right = mid;
} else {
left = mid;
}
}
cout << fixed << setprecision(10) << right << endl;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |