[골4] 4386 - 별자리 만들기

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

#pragma region 빠른 입출력

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

#pragma endregion

using namespace std;
using dp = pair<double, double>;

#define MAX 101
#define x first
#define y second

vector<dp> star;
vector<pair<double, dp>> coord;
int parent[MAX];
double ans;

int GetParent(int a)
{
	return (parent[a] == a) ? a : parent[a] = GetParent(parent[a]);
}

void Union(int a, int b)
{
	a = GetParent(a), b = GetParent(b);

	if (a < b)
		parent[b] = a;

	else
		parent[a] = b;
}

bool Find(int a, int b)
{
	a = GetParent(a), b = GetParent(b);
	return a == b;
}

int main()
{
	FAST_IO();
	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		double x, y;
		cin >> x >> y;
		star.push_back({ x, y });
	}

	// 두 점 사이 거리를 저장
	for (int i = 0; i < star.size(); i++)
	{
		double x1 = star[i].x, y1 = star[i].y;

		for (int j = i + 1; j < star.size(); j++)
		{
			double x2 = star[j].x, y2 = star[j].y;
			double dist = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
			coord.push_back({ dist,{i, j} });
		}
	}
	sort(coord.begin(), coord.end());

	for (int i = 0; i <= n; i++)
		parent[i] = i;

	for (int i = 0; i < coord.size(); i++)
	{
		double d = coord[i].x;
		double a = coord[i].y.x, b = coord[i].y.y;

		if (!Find(a, b))
		{
			Union(a, b);
			ans += d;
		}
	}
	cout << ans;
	return 0;
}