https://www.acmicpc.net/problem/4386
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)
둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.
첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.
그동안 풀었던 MST문제들과는 다르게 간선을 직접 계산해서 추가해주어야합니다. 실수형으로 입력되므로 Edge 구조체를 선언시에 가중치(w부분)을 실수형을 사용하였습니다.
소수점 2번째 자리까지 출력하기 위해서 c++ 문법인 fixed를 사용해도 되지만 c문법인 .2f를 사용하였습니다.
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define MAX 1005
#define INF 1e9+7
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdbl = pair<double, double>;
using vi = vector<int>;
#define sz(a) int((a).size())
struct UnionFind {
vector<int> parent, rank, cnt, check;
UnionFind(int n) : parent(n), rank(n, 1), cnt(n, 1), check(n) {
iota(parent.begin(), parent.end(), 0);
}
int Find(int x) {
return x == parent[x] ? x : parent[x] = Find(parent[x]);
}
bool Union(int a, int b) {
a = Find(a), b = Find(b);
if (a == b) return 0;
if (rank[a] < rank[b]) swap(a, b);
parent[b] = a;
rank[a] += rank[a] == rank[b];
cnt[a] += cnt[b];
check[a] |= check[b];
return 1;
}
};
struct Edge{
int u,v;
double w;
Edge(int u1,int v1, double w1): u(u1),v(v1),w(w1){}
bool operator < (const Edge& O)const{ return w < O.w; }; // 오름차순 정렬
};
int main(){
fastio;
int n; cin >> n;
vector<pdbl> point(n);
vector<Edge> e;
for(int i = 0; i < n; i++){
double a,b; cin >> a >> b;
point[i].x = a; point[i].y = b;
}
// 거리 계산
for(int i = 0; i < point.size(); i++){
for(int j = i + 1; j < point.size(); j++){
double c = sqrt(((point[i].x - point[j].x) * (point[i].x - point[j].x)) + ((point[i].y - point[j].y)*(point[i].y - point[j].y)));
e.pb(Edge(i ,j ,c));
}
}
sort(e.begin(), e.end()); // 가중치 기준으로 정렬
UnionFind UF(n);
double result = 0;
int cnt = 0;
for(int i = 0; ; i++){
if(UF.Union(e[i].u, e[i].v)){
result += e[i].w;
if(++cnt == n - 1) break; // n - 1개 간선을 뽑으면 탈출
}
}
printf("%.2f\n",result);
return 0;
}