#include <bits/stdc++.h>
#define ll long long
using namespace std;
long double eps = 0.0000000001;
long double g[1001][1001];
int used[1001];
int n, cnt ;
long double length(ll x1,ll y1,ll x2, ll y2)
{
long double s = sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
return s;
}
void dfs(int v,long double mid)
{
used[v] = 1;
for(int i = 1; i <= n; i++)
if(mid >= g[v][i] and used[i] == 0)
dfs(i,mid);
cnt++;
}
bool check(long double mid)
{
for(int i = 1; i <= n; i++)
{
used[i] = 0;
}
cnt = 0;
dfs(1,mid);
if(cnt == n)
return true;
else
return false;
}
void answer()
{
ll x, y;
vector <pair <ll,ll > > v;
v.push_back({0,0});
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> x >> y;
v.push_back({x, y});
}
long double mx = eps;
for(int i = 1; i < n; i++)
for(int j = i + 1; j <= n; j++)
{
g[i][j] = length(v[i].first, v[i].second, v[j].first, v[j].second);
g[j][i] = g[i][j];
mx = max(mx, g[i][j]);
}
long double l = eps, r = mx;
while((r - l) >= eps)
{
long double mid = (l + r) / 2;
if(check(mid))
r = mid;
else
l = mid + eps;
}
r /= 2;
cout << fixed << setprecision(7) << r;
}
int main()
{
int t = 1;
// cin >> t;
while(t--)
answer();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
588 KB |
Output is correct |
| 5 |
Correct |
3 ms |
844 KB |
Output is correct |
| 6 |
Correct |
15 ms |
6240 KB |
Output is correct |
| 7 |
Correct |
26 ms |
6244 KB |
Output is correct |
| 8 |
Correct |
61 ms |
12108 KB |
Output is correct |
| 9 |
Correct |
128 ms |
16012 KB |
Output is correct |
| 10 |
Correct |
152 ms |
15948 KB |
Output is correct |
