[Algorithm]Baekjoon 1004번 :: 어린 왕자

https://www.acmicpc.net/problem/1004

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
 
 
bool isContain(int cy, int cx, int cr, int py, int px) 
{
    int distance = pow(cy - py, 2) + pow(cx - px, 2);
    cr *= cr;
 
    if (distance < cr)
    {
        return true;
    }
 
    return false;
}
 
int t, sy, sx, dy, dx, n, y, x, r, a, b, c;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t;
 
    vector<int> answers;
 
    while (t--)
    {
        cin >> sy >> sx >> dy >> dx >> n;
 
        int startCount = 0;
        int destCount = 0;
 
        for (int i = 0; i < n; ++i)
        {
            cin >> a >> b >> c;
 
            bool check = false;
 
            if (isContain(a, b, c, sy, sx))
            {
                ++startCount;
                check = true;
            }
 
            if (isContain(a, b, c, dy, dx))
            {
                ++destCount;
                if (check)
                {
                    --startCount;
                    --destCount;
                }
            }
        }
 
        answers.push_back(startCount + destCount);
    }
 
    for (auto answer : answers)
    {
        printf("%d\n", answer);
    }
}

 

어린왕자가 목표지점까지 갈 때 몇개의 원을 통과하는지 구하는 문제이다.

 

기본적으로 시작점, 도착점을 몇개의 원이 둘러싸고 있는지를 구하는 문제이다.

원안에 점이 포함되고있는지를 구하는것은, 점과 원의 중점과의 거리를 구한 후, 원의 반지름보다 작으면 원 안에 포함되어있는 것이고 아니면 바깥에 있는 것이다.

이런식으로 도착점, 시작점각각 둘러싸고있는 원의 개수를구해서 더해주면 된다.

 

물론 여기서 끝은 아니고, 시작점, 도착점 둘 다를 둘러싸고있는 큰 원이 있는 경우가 있다. 이 원은 우주선이 통과할 일이 없기 때문에, 카운팅에서 반드시 빼줘야 한다.

그래서 코드를 보면 시작점을 먼저 포함검사를 해주고, 포함할 경우 체크를 해놨다가 도착점마저 포함하고있는 원일경우엔 각각 -- 연산을 해줬다.