#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
const int N = 1010, F = 1e9;
int n;
struct P{
ll x, y;
double dist(P a){
return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y));
}
};
bool check(vector<vector<int>> &g){
queue<int> q;
vector<bool> v(1001, 0);
q.push(0);
v[0] = 1;
while(!q.empty()){
int x = q.front();
q.pop();
for(int u: g[x]){
if(!v[u]){
v[u] = 1;
q.push(u);
}
}
}
bool ok = 1;
for(int i=0;i<n;i++) ok&=v[i];
return ok;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
P arr[N];
cin >> n;
for(int i = 0; i < n; i++) cin >> arr[i].x >> arr[i].y;
double l = 0, r = 2*F, ans = 2*F;
while(l + (0.000001f) < r){
double mid = (l+r)/2.0;
vector<vector<int>> g(N);
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
double d = arr[i].dist(arr[j]);
if(d <= mid){
g[i].pb(j);
g[j].pb(i);
}
}
}
if(check(g)){
ans = min(ans, mid);
r = mid;
}else l = mid;
}
cout << fixed << setprecision(15);
cout << l/2.0;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
4 ms |
332 KB |
Output is correct |
| 5 |
Correct |
4 ms |
332 KB |
Output is correct |
| 6 |
Correct |
106 ms |
1388 KB |
Output is correct |
| 7 |
Correct |
94 ms |
1404 KB |
Output is correct |
| 8 |
Correct |
209 ms |
3496 KB |
Output is correct |
| 9 |
Correct |
262 ms |
4652 KB |
Output is correct |
| 10 |
Correct |
192 ms |
4556 KB |
Output is correct |
