#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define sz(a) (int)a.size()
#define ll long long
#define ld long double
const int N = 3e5 + 100;
ld dist(ll x, ll y, ll x1, ll y1)
{
return sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
}
int dsu[N], rang[N];
int pred(int a)
{
if(a == dsu[a]) return a;
return dsu[a] = pred(dsu[a]);
}
void unite(int a, int b)
{
a = pred(a);
b = pred(b);
if(rang[a] > rang[b])
{
swap(a, b);
}
dsu[b] = a;
if(rang[a] == rang[b])
{
rang[a]++;
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector <int> x(n), y(n);
for(int i = 0; i < n; i++)
{
dsu[i] = i;
rang[i] = 1;
cin >> x[i] >> y[i];
}
vector <pair <ld, pair <int, int> > > mass;
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
mass.push_back({dist(x[i], y[i], x[j], y[j]), {i, j}});
}
}
sort(mass.begin(), mass.end());
int cnt = 0;
for(int i = 0; i < sz(mass); i++)
{
if(pred(mass[i].Y.X) != pred(mass[i].Y.Y))
{
cnt++;
if(cnt == n - 1)
{
cout << fixed << setprecision(10) << mass[i].X / 2;
return 0;
}
unite(mass[i].Y.X, mass[i].Y.Y);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
2 ms |
716 KB |
Output is correct |
| 6 |
Correct |
29 ms |
4536 KB |
Output is correct |
| 7 |
Correct |
29 ms |
4544 KB |
Output is correct |
| 8 |
Correct |
72 ms |
16820 KB |
Output is correct |
| 9 |
Correct |
120 ms |
16824 KB |
Output is correct |
| 10 |
Correct |
119 ms |
16824 KB |
Output is correct |
