문제 URL :www.acmicpc.net/problem/10216
10216번: Count Circle Groups
백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었��
www.acmicpc.net
문제접근법 : 수학적인 접근이 필요합니다. 두원의 위치관계만 알고 union- find만 해주면되기 때문에
어려운 문제는 아닙니다.
대표적으로 두원의 위치관계를 풀기위한 문제는 www.acmicpc.net/problem/1002
1002번: 터렛
각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.
www.acmicpc.net
터렛 문제가 대표적이니 한번 풀어보시길 바랍니다.
이 이미지는 mathbang.net/101에서 가져왔습니다.
결국엔 거리 d가 반지름 r1+r2보다 크면 만나지않고 그외는 모두 원이 만나거나 내부에 포함하기 때문에 4번식 한가지만 선택해서 풀었습니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
//By 콩순이냉장고
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cmath>
using namespace std;
vector<tuple<int, int, int>> v;
int parent[3001];
int find(int idx){
if (idx == parent[idx])
return idx;
return parent[idx] = find(parent[idx]);
}
int Distance(int x1, int y1, int x2, int y2)
{
return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
}
void Union(int idx1, int idx2){
idx1 = find(idx1);
idx2 = find(idx2);
if (idx1 == idx2)
return;
parent[idx2] = idx1;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test;
cin >> test;
while (test--){
v.clear();
int n;
cin >> n;
int visit[3001] = { 0 };
for (int i = 0; i < n; i++){
int x, y, r;
cin >> x >> y >> r;
v.push_back(make_tuple(x, y, r));
parent[i] = i;
}
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
int x1, y1, r1;
int x2, y2, r2;
tie(x1, y1, r1) = v[i];
tie(x2, y2, r2) = v[j];
int dis = Distance(x1, y1, x2, y2);
int t = (r1 + r2)*(r1 + r2);
if (t < dis)
continue;
Union(i, j);
}
}
int cnt = 0;
for (int i = 0; i < n; i++){
visit[find(i)]++;
}
for (int i = 0; i < n; i++)
{
if (visit[i])
cnt++;
}
cout << cnt << "\n";
}
}
|
cs |
모르는점 혹은 궁금한점 혹은 논리적인 오류가 있다면 언제든지 댓글을 이용해주시길 바랍니다.
'백준' 카테고리의 다른 글
| 백준 1107 리모컨 (0) | 2020.11.29 |
|---|---|
| 백준 16562 친구비 (0) | 2020.10.02 |
| 백준 5373 큐빙(SW 역량 테스트 기출 문제) (0) | 2020.09.21 |
| 백준 4195 친구 네트워크 (0) | 2020.08.30 |
| 백준 4386 별자리 만들기 (0) | 2020.08.30 |
