[C++] 백준 1004 어린 왕자

https://www.acmicpc.net/problem/1004
제목 : 어린 왕자
solved.ac 난이도 : Silver III

나의 풀이

행성계의 진입/이탈 횟수를 구하는 문제로 행성에서 이탈을 한다 라고 하면 두 가지 경우를 생각 해볼 수 있다.

1. 시작점이 행성계 안에 있고 도착점이 행성계 밖에 있다.
2. 시작점이 행성계 밖에 있고 도착점이 행성계 안에 있다.

그렇다면 시작점과 도착점이 행성계 안에 있다는 것을 어떻게 표현을 할 수가 있는가?
그것은 주어진 행성계의 반지름을 이용하면 된다.
문제에서 행성계의 중점과 반지름을 제공해주기 때문에 우리의 시작점과 도착점 각각과 행성계 중심 사이의 거리를 구하여 반지름과 비교를 해보면 된다.
두 거리를 구한다음 위에 두가지의 경우에만 진입/이탈 횟수를 측정해주면 된다.

정답 코드

#include <iostream>
#include <cmath>
#include <vector>
#include <tuple>

using namespace std;

int getrange(int x, int y, int cx, int cy) {
    int rx = x - cx;
    int ry = y - cy;
    return rx * rx + ry * ry;
} // 두 점 사이의 거리를 제곱 형태로 반환

int getcirclecount(vector<tuple<int, int, int>>& circle, int x1, int y1, int x2, int y2) {
    /*
        1. 출발지점과 도착지점 둘다 원의 바깥에 있으면 카운트 안함.
        2. 둘다 같은 원 안에 있으면 카운트 안함.
    */
    int count = 0;
    for (auto c : circle) {
        int fromstart = getrange(x1, y1, get<0>(c), get<1>(c));
        int fromend = getrange(x2, y2, get<0>(c), get<1>(c));
        int rot = get<2>(c) * get<2>(c); 
        // 두 점 사이의 거리도 제곱으로 반환 받았으니 반지름도 제곱하여 비교
        if (fromstart < rot && fromend > rot) {
            count++;
        }
        else if (fromstart > rot && fromend < rot) {
            count++;
        }
    }
    return count;
} 

int main()
{
    int T, x1, y1, x2, y2, n, cx, cy, r;
    vector<pair<int, int>> circle;
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        vector<tuple<int, int, int>> circle;
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> cx >> cy >> r;
            circle.push_back({ cx, cy, r });
        }
        cout << getcirclecount(circle, x1, y1, x2, y2) << "\n";
    }
}

두 점 사이의 거리가 루트를 씌우게 되면 소수점이 나오는 경우가 있어 비교가 까다롭다. 그래서 두 점 사이의 거리의 제곱근을 구하는것 보다 반지름을 제곱하여 비교를 하였다.