1004)어린 왕자

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

시작점에서 도착점까지 행성계를 진입/이탈 하는 최소 횟수를 구해야 한다.

되게 어려워 보이지만 잘 관찰해보면 점이 원 내부에 있는가 외부에 있는가에 따라 진입/이탈 횟수가 결정됨을 알 수 있다.

위 그림에서 왼쪽 빨간 점은 아주 큰 행성계 하나에만 포함되어 있고

오른쪽 빨간 점은 두 개의 행성계에 포함되어 있다.

각 점이 행성계에 몇 번 포함됬냐에 따라 진입/이탈 횟수를 쉽게 알 수 있다.

어떤 점이 원 안에 포함됬는 지 여부를 확인 하려면 P(x0, y0)을 C : (x-a)^2 + (y-b)^2에 대입했을 때

C(x0,y0) > r^2이면 점이 원 바깥에 있고 C(x0,y0) < r^2이면 점은 원 안에 있다.

그림처럼 두 점이 같은 행성계에 포함되면 진입/이탈을 할 필요가 없다.

두 점이 각 원에 대해 포함 여부를 파악하고 각 포함 여부를 XOR 연산해 참인 경우를 세어 출력하면 된다.

#include<stdio.h>
 
typedef struct _Point {
    int x;
    int y;
}Point;
 
typedef struct _Circle {
    int x;
    int y;
    int r;
}Circle;
 
typedef enum _BOOL {
    TRUE = 1, FALSE = 0
}Bool;
 
int power(int a) {
    return a*a;
}
 
Bool isInsideCircle(Circle circle, Point point) {
    if (power(point.x - circle.x) + power(point.y - circle.y) > power(circle.r)) return FALSE;
    else return TRUE;
}
 
int main() {
    int n, m;
    Point point[2];
    Circle circle[50];
    Bool isInside[2][50] = {FALSE};
    int count;
 
    scanf("%d",&n);
    for (int i = 0; i < n;i++) {
        for (int j = 0; j < 2;j++) scanf("%d %d", &point[j].x, &point[j].y);
        scanf("%d",&m);
        
        for (int j = 0; j < m;j++) {
            scanf("%d %d %d",&circle[j].x, &circle[j].y, &circle[j].r);
        }
 
        for (int j = 0; j < 2;j++) {
            for (int k = 0; k < m;k++) {
                isInside[j][k] = isInsideCircle(circle[k], point[j]);
            }
        }
        
        count = 0;
        for (int j = 0; j < m;j++) {
            if (isInside[0][j] ^ isInside[1][j]) count++;
        }
 
        printf("%d\n",count);
    }
 
    return 0;
}