[백준][C++] 10216: Count Circle Groups

문제 링크: https://www.acmicpc.net/problem/10216

 

disjoint set 문제인데요, 모든 \((A_i, A_j)\) 쌍에 대해서 인접하는지 통신영역이 겹치는지 체크하고 겹칠 때만 merge를 해주면 됩니다.

\[distance(A_i, A_j) \leq r_i + r_j\]

두 원의 위치관계를 대충 생각해보면 위 식이 true일때만 합쳐야 합니다.

여기서 distance는 두 점 사이의 거리이고, 맨해튼 거리(manhattan distance)가 아닌 유클리드 거리입니다. 아무 생각 없이 맨해튼 거리로 했다가 몇번 틀렸네요

#include <bits/stdc++.h>
using namespace std;

vector<int> parent;
vector<tuple<int, int, int>> posts;

void init(int sz) {
	parent.resize(sz);
	for (int i = 0; i < sz; ++i)
		parent[i] = i;
}

int find(int u) {
	if (u == parent[u]) return u;
	return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	parent[u] = v;
}

//쓰지마세용
//int man_dist(int y1, int x1, int y2, int x2) {
//	return abs(y2 - y1) + abs(x2 - x1);
//}

int sq(int x) {
	return x * x;
}

int dist_sq(int y1, int x1, int y2, int x2) {
	return sq(y2-y1) + sq(x2-x1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int t;
	cin >> t;

	while (t--) {
		int n;
		cin >> n;
		init(n);
		posts.clear();

		int x, y, r;
		for (int i = 0; i < n; ++i) {
			cin >> x >> y >> r;
			posts.emplace_back(x, y, r);
		}


		int ans = n;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				if (find(i) == find(j)) continue;

				auto& [x1, y1, r1] = posts[i];
				auto& [x2, y2, r2] = posts[j];

				if (dist_sq(y1, x1, y2, x2) <= sq(r1+r2)) {
					merge(i, j);
					--ans;
				}
			}
		}

		cout << ans << '\n';
	}

	return 0;
}