| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1152302 | Sandarach151 | Odašiljači (COCI20_odasiljaci) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
vector<pair<double, pair<int, int> > > vect;
vector<int> sze;
vector<int> link;
int find(int a){
while(a!=link[a]){
a = link[a];
}
return a;
}
bool same(int a, int b){
return find(a)==find(b);
}
void unite(int a, int b){
a = find(a);
b = find(b);
if(sze[a]<sze[b]){
swap(a, b);
}
link[b]=a;
sze[a]+=sze[b];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
pair<int, int> points[n];
sze.assign(n, 1);
for(int i=0; i<n; i++){
link.push_back(i);
}
for(int i=0; i<n; i++){
int a, b;
cin >> a >> b;
points[i] = make_pair(a, b);
}
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
vect.push_back(make_pair(sqrt(pow(points[i].first-points[j].first, 2) + pow(points[i].first-points[j].first, 2)), make_pair(i, j)));
}
}
sort(vect.begin(), vect.end());
int cnt = 0;
double ans = 0;
for(int i=0; i<vect.size(); i++){
int a = vect[i].second.first;
int b = vect[i].second.second;
if(!same(a, b)){
unite(a, b);
cnt += 1;
ans = vect[i].first / 2;
}
if(cnt==n*(n-1)/2) break;
}
cout << ans << '\n';
return 0;
}