728x90
n개의 행성계의 범위를 입력받을 때 출발점이 해당 행성계에 포함되는지, 도착점이 해당 행성계에 포함되는지를 벡터에 저장해주었다. 출발점이 포함되는지 여부는 v[i].first에, 도착점이 포함되는지 여부는 v[i].second에 저장해주었다.
포함되는지 아닌지는 행성계의 중심과 출발점 (또는 도착점) 사이의 거리가 행성계의 반지름의 길이보다 큰지 아닌지를 판단해주었다.
예를 들어 행성계의 중심이 (a, b), 반지름이 r이고 출발점이 (c, d)일 때
두 점 (a, b)와 (c, d) 사이의 거리인 √(a - c)^2 + (b - d)^2가 r보다 크면 출발점 (c, d)는 행성계에 포함되지 않는다.
하지만 정수에서 루트를 씌우면 실수가 되어 부정확해진다. 따라서 그냥 (a - c)^2 + (b - d)^2와 r^2을 비교해주었다.
그렇게 출발점과 도착점이 행성계에 포함되는지 아닌지 n개의 행성계를 판단하여 포함되면 true, 포함되지 않으면 false를 저장해준다.
포함 여부가 모두 일치한다면 출발점과 도착점은 같은 행성계에 있으므로 진입, 이탈 횟수는 0이다.
포함 여부가 하나만 다르다면 진입/이탈 횟수는 1이 된다. 이런 식으로 풀었다.
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
int testCase;
cin >> testCase;
int x1, x2, y1, y2, n, cx, cy, r, cnt;
for (int t = 0; t < testCase; t++) {
cnt = 0;
cin >> x1 >> y1 >> x2 >> y2 >> n;
vector<pair<bool, bool>> v(n);
for (int i = 0; i < n; i++) {
cin >> cx >> cy >> r;
if (pow(cx - x1, 2) + pow(cy - y1, 2) > r * r) {
v[i].first = false;
}
else {
v[i].first = true;
}
if (pow(cx - x2, 2) + pow(cy - y2, 2) > r * r) {
v[i].second = false;
}
else {
v[i].second = true;
}
}
for (int i = 0; i < n; i++) {
if (v[i].first != v[i].second) {
cnt++;
}
}
cout << cnt << '\n';
}
return 0;
}
728x90
'알고리즘 문제' 카테고리의 다른 글
[백준] 1992번 쿼드트리 (0) | 2021.01.05 |
---|---|
[백준] 1074번 Z (0) | 2021.01.04 |
[백준] 11866번 요세푸스 문제 0 (0) | 2021.01.03 |
[백준] 2217번 로프 (0) | 2021.01.02 |
[백준] 10799번 쇠막대기 (0) | 2021.01.02 |