[BAEKJOON] 1004번

 

 

결국 최대한 원 안에 들어가지 않고 출발점에서 도착점으로 갈 때 몇 개에 원을 지나야 하는지,

즉 지나지 않고는 도착점에 갈 수 없는 원만 지날 때 그 원의 수가 몇 개인지 구하는 문제다.

 

무조건 지나야만 하는 원은 어떤 것이 있을까? 경로의 길이에는 제한이 없으므로 얼마든지 우회할 수 있다.

우회할 수 없는 원은 딱 두 가지다.

 

① 출발점을 둘러싸는 원

② 도착점을 둘러싸는 원

 

점을 둘러싸는 원 안에 진입하지 않고는 절대 도착점에 도달할 수 없으므로 최소한으로 지나는 원의 수는 이런 원의 수가 된다.

따라서 원이 주어질 때마다 출발점이나 도착점이 그 원 안에 있는지 검사하면 된다.

이 때 출발점과 도착점을 모두 둘러싸는 원은 포함되지 않는다. 이런 원은 우회할 수도 없고 그럴 필요도 없기 때문이다.

 

출발점과 도착점 모두 둘러싸지 않는 원(우회해야 하는 원): C, D, E

출발점과 도착점을 모두 둘러싸는 원(우회할 수도 필요도 없는 원): G

출발점과 도착점 중 하나만 둘러싸는 원(우회할 수 없는 원): A, B, F

 

따라서 이 경우 정답은 3이 된다.

 

 

매 테스트 케이스에서 원의 좌표, 반지름을 입력받을 때마다 그 원에 출발점이나 도착점이 포함되는지 검사하면 된다.

#include <stdio.h>
 
int main()
{
    int t, n;
    int srcX, srcY, destX, destY;
    int cX, cY, r;
    int count;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d %d %d", &srcX, &srcY, &destX, &destY);
        count = 0;
        scanf("%d", &n);
        while (n--)
        {
            scanf("%d %d %d", &cX, &cY, &r);
            if ((((srcX - cX) * (srcX - cX)) + ((srcY - cY) * (srcY - cY)) <= r * r)
            != (((destX - cX) * (destX - cX)) + ((destY - cY) * (destY - cY)) <= r * r))
            {
                ++count;
            }
        }
 
        printf("%d\n", count);
    }
 
    return 0;
}

17행

행성계(원)의 중심좌표와 반지름을 입력받는다.

 

18~19행

17행에서 입력받은 원에 출발점이나 도착점이 포함되는지 확인한다.

즉 출발점 좌표 $(srcX,\;srcY)$와 입력받은 원 $(x-cX)^2+(y-cY)^2=r^2$에 대해

$(srcX-cX)^2+(srcY-cY)^2 \leq r^2$가 성립하는지 확인하고 마찬가지로 도착점 좌표 $(destX,\;destY)$에 대해서도 $(destX-cX)^2+(destY-cY)^2 \leq r^2$가 성립하는지 확인한다. 이 때 둘 중 하나는 참이고 하나는 거짓인 원만 count해야 하므로 두 식의 결과가 다를 때만 $++count;$를 실행한다.