#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 1e3 + 10;
const double INF = 1e18;
void solve() {
vector<int> vt;
int n;
cin >> n;
double a[n + 1];
double b[n + 1];
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
if(n == 1) {
cout << 0.0000000 << endl;
return;
}
double l = 1, r = 1e9, best = -1, ep = 0.0000001;
while(r - l >= ep) {
vector<int> adj[n + 5];
vector<int> vis(n + 5, 0);
queue<int> q;
double m = (l + r) / 2.00;
for(int i = 1; i <= n; i++) {
for(int j = i + 1; j <= n; j++) {
if(sqrt((abs(a[i] - a[j]) / 2) * (abs(a[i] - a[j]) / 2) + (abs(b[i] - b[j]) / 2) * (abs(b[j] - b[i]) / 2)) <= m) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
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 check = true;
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
check = false;
}
}
if(check) {
r = m;
best = m;
}
else {
l = m;
}
}
cout << setprecision(7) << fixed << best << endl;
}
signed main(){
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |