#include<bits/stdc++.h>
#define fast(); ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld double
using namespace std;
ll n, N=1005, oo=1e9;
ld l=0,r=2*oo,kq=2*oo;
struct Point
{
ll x, y;
ld dd(Point 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()
{
Point a[N];
fast();
// freopen ("odasiljaci.inp", "r", stdin);
// freopen ("odasiljaci.out", "w", stdout);
cin >> n;
for(int i=0;i<n;i++) cin>>a[i].x>>a[i].y;
while(l + (0.000001f) < r)
{
ld giua = (l+r)/2.0;
vector<vector<int>> g(N);
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
ld d = a[i].dd(a[j]);
if(d <= giua){
g[i].push_back(j);
g[j].push_back(i);
}
}
}
if(check(g))
{
kq=min(kq, giua);
r=giua;
}
else l=giua;
}
cout<<fixed<<setprecision(7);
cout<<l/2.0;
}
// 7 2 3 3 4 4 5 0 1 3 1 4 2 1 5
| # |
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 |
3 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 |
100 ms |
1404 KB |
Output is correct |
| 7 |
Correct |
92 ms |
1412 KB |
Output is correct |
| 8 |
Correct |
215 ms |
3468 KB |
Output is correct |
| 9 |
Correct |
261 ms |
4664 KB |
Output is correct |
| 10 |
Correct |
196 ms |
4684 KB |
Output is correct |
