[C] 백준 1004번 (어린 왕자)

출발점과 도착점 그리고 원이 주어진다.

이 때, 출발점에서 도착점까지 갈 때 지나가야 하는 원의 최소 개수를 출력하는 것이 문제다.

(문제 원문에서 '행성계'라고 한 것을 그냥 원이라고 생각하면 된다)

 

'지나가야 하는 원의 최소 개수'라는 표현이 잘 와닿지 않는다면, '지나갈 수 밖에 없는 원의 개수' 라고 생각하면 좀 더 쉬울 것 같다.

그렇다면, '지나갈 수 밖에 없는' 원은 어떤 원일까? 바로, 원 내부에 출발점 또는 도착점이 있는 경우이다.

 

출발점에서 도착점까지 가려면 빨간색 원을 '지나갈 수 밖에' 없다.

 

따라서, 출발점을 포함하는 원의 개수와 도착점을 포함하는 원의 개수를 다 더 해주면 되는데, 한 가지 주의할 점이 있다.

출발점과 도착점이 하나의 원 안에 있다

 

이런 경우에는 원을 하나도 지나가지 않고 출발점에서 도착점까지 갈 수 있다. 

즉, 출발점'만' 포함하는 원과 도착점'만' 포함하는 원의 개수를 더해주면 된다.

출발점과 도착점을 같이 포함하는 원의 개수를 더하면 안된다.

 

이제 마지막으로 하나만 생각하면 된다. 

점이 원 내부에 있는지 외부에 있는지 어떻게 알 수 있을까?

원의 방정식을 생각해보자. 원의 중심을 (a,b)라고 하면

(x-a)² + (y-b)² = r² 을 만족시키는 x, y에 대해서 점(x, y)는 원을 이루는 하나의 점이 된다. 즉 원 위에 있는 점이 된다.

(x-a)² + (y-b)² < r² 이 식을 만족시키는 x,y라면 어떨까? 이 경우, 점(x, y)는 원의 내부에 위치하게 된다.

 

지금까지 생각해낸 것들을 코드로 옮기기만 하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

int main() {
    int t; scanf("%d", &t);
    int x1, y1, x2, y2, n, result; //출발점의 좌표 (x1, y1), 도착점의 좌표(x2, y2), result는 출력값
    int cx[50], cy[50], r[50]; 
    // cx[0], cy[0], r[0]는 각각 1번째 원의 x좌표, y좌표, 반지름
    // cx[1] , cy[1], r[1]은 각각 2번째 원의 x좌표, y좌표, 반지름
    
    while (t--) {
        result = 0;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &cx[i], &cy[i], &r[i]);
        }
        
        for (int i = 0; i < n; i++) {
            if (pow(x1 - cx[i], 2) + pow(y1 - cy[i], 2) < pow(r[i], 2)) {
                if (pow(x2 - cx[i], 2) + pow(y2 - cy[i], 2) < pow(r[i], 2)) continue;
                result++;
            }
            else if (pow(x2 - cx[i], 2) + pow(y2 - cy[i], 2) < pow(r[i], 2)) {
                if (pow(x1 - cx[i], 2) + pow(y1 - cy[i], 2) < pow(r[i], 2)) continue;
                result++;
            }
        }    
        
        printf("%d\n", result);
    }
}

 

 

+) 문제를 풀다가 아래 그림과 같은 상황에는 어떻게 해야 하나 생각했을 수도 있는데

 

 

빨간색 원 안에 출발점이 있고, 파란색 원들이 빨간색 원을 '빈틈없이' 감싸고 있다. 이런 경우라면, 계산이 복잡해질텐데 다행히도 이 문제에서는 "행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다." 라는 조건이 있다. 이 조건 덕분에 원은 전부 서로서로 간격을 둬야 한다. 그 간격 사이로 지나가면 되므로 개수를 셀 필요가 없다.