[백준] 4386번 별자리 만들기 C++

문제 출처: https://www.acmicpc.net/problem/4386

4386번: 별자리 만들기

좌표들을 받아서 두 점 사이의 거리를 계산 한 뒤 MST로 구할 수 있다.

#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstring>

using namespace std;

struct P {
	int a, b;
	double dist;
};

bool cmp(P a, P b) {
	return a.dist < b.dist;
}

double dist(double x1, double y1, double x2, double y2) {
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int u[101];
 
int find(int a) {
	if (u[a] < 0)return a;

	return u[a] = find(u[a]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return;
	
	if (u[a] < u[b]) {
		u[a] += u[b];
		u[b] = a;
	}
	else {
		u[b] += u[a];
		u[a] = b;
	}
}


int main(void)
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


	int n; cin >> n;


	
	double pos[101][2];
	P arr[10001];

	memset(u, -1, sizeof(u));

	for (int i = 0; i < n; i++) {
		cin >> pos[i][0] >> pos[i][1];
	}

	int count = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j)continue;
			double val = dist(pos[i][0], pos[i][1], pos[j][0], pos[j][1]);
			arr[count] = { i,j,val };
			count++;
		}
	}

	sort(arr, arr+count, cmp);

	double sum = 0;

	for (int i = 0; i < count; i++) {
		P curr = arr[i];
		if (find(curr.a) == find(curr.b))continue;
		else {
			merge(curr.a, curr.b);
			sum += curr.dist;
		}
	}


	printf("%0.2lf", sum);


	

}