#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e3;
struct Point
{
long long x,y;
};
long long d(Point a,Point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int fau[N+10];
Point p[N+10];
vector<tuple<long long,int,int>> srt;
int f(int x)
{
return (fau[x]==x ? fau[x]:fau[x]=f(fau[x]));
}
void u(int x,int y)
{
fau[f(y)]=f(x);
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
fau[i]=i;
cin>>p[i].x>>p[i].y;
for(int j=1;j<i;j++)
srt.emplace_back(d(p[j],p[i]),j,i);
}
sort(srt.begin(),srt.end());
long long mx=0;
for(auto [c,a,b]:srt)
{
if(f(a)!=f(b))
{
mx=c;
u(a,b);
}
}
cout<<fixed<<setprecision(7);
cout<<sqrtl((long double)mx)/2<<"\n";
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 |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
18 ms |
2504 KB |
Output is correct |
| 7 |
Correct |
18 ms |
2504 KB |
Output is correct |
| 8 |
Correct |
44 ms |
8596 KB |
Output is correct |
| 9 |
Correct |
59 ms |
8592 KB |
Output is correct |
| 10 |
Correct |
61 ms |
8640 KB |
Output is correct |
