1004: 어린 왕자

어떤 문제인가?

딱 한 점만 포함하는 원의 개수가 몇 개인지 묻는 문제.

시행착오 횟수

한 번에 성공함.

1차 시도: AC

그림을 보면 곡선이 들어가 있어서 어렵게 느껴질 수 있으나, 문제는 최소한의 행성계 진입/이탈 횟수만을 묻고 있다. 문제에 여러 조건이 달려 있는데, 이들을 이용하는 것이 핵심이다.

1. 행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다.
2. 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다.

그림을 그려보면 이 문제는 결국 다음처럼 바꿔쓸 수 있음을 알 수 있다.

오로지 딱 한 점만 포함하는 원이 얼마나 있는가?

어떤 점이 원 안에 있을 조건은 아주 단순하다. 심지어 점이 원의 경계에 있는 경우도 주어지지 않으니 다음처럼 편하게 쓸 수 있다.

딱 한 점만 주어진 원 안에 있는 경우만 구하면 되므로, XOR 연산까지 버무리면 쉽게 풀 수 있다.
이제 이걸 코드로 옮겨보자.

#include <stdio.h>
#include <stdlib.h>
#define POW(a) (a) * (a)

int T;

int main() {
    scanf("%d", &T);
    for(int i = 0; i < T; i++) {
        int x1, y1, x2, y2, n, *c, a = 0;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &n);
        c = calloc(3 * n, sizeof(int));

        for(int j = 0; j < 3 * n; j += 3) {
            scanf("%d%d%d", &c[j], &c[j+1], &c[j+2]);
            if((POW(x1 - c[j]) + POW(y1 - c[j+1]) < POW(c[j+2])) 
                ^ (POW(x2 - c[j]) + POW(y2 - c[j+1]) < POW(c[j+2])))
                a++;
        }
        printf("%d\n", a);
    }
}

다른 분들의 풀이

사실 배열을 쓸 필요도 없었다. 매 입력마다 원의 원점과 반지름값을 새로 받아와도 된다.
풀이 원리는 매우 유사하므로 생략하겠다.