[C 터렛] 백준 1002

문제의 중요한 조건은 두 터렛의 좌표와 거리를 이용해서 원의 외부, 외접, 내접, 내부, 일치를 판별하는 것이다.

두 터렛 사이의 거리가 각 터렛에서

0) 마린까지의 거리가 일치하고 두 터렛의 위치가 일치하면 일치

1) 마린까지의 거리의 합보다 크면 외부

2) 마린까지의 거리의 차보다 작으면 내부

3) 마린까지의 거리의 합과 같으면 외접

4) 마린까지의 거리의 차와 같으면 내접

5) 마린까지의 거리의 차보다 크고 합보다 작으면 두 점에서 만난다.

원래대로라면 두 점 사이의 거리는 전부 제곱근을 이용해야하지만 제곱근을 구하는 것 보다 반대쪽을 제곱하는 편이 유리하니 이 방법을 사용하도록 한다.

testcase는 반드시 0이상의 정수이므로 unsigned

r1, r1은 자연수지만 뺄셈에서 결과를 위해 signed

굳이 복잡한 곱셈을 할 필요 없는 일치 판별을 가장 먼저

length의 제곱근을 구하기보단 min, max를 제곱하는 쪽으로 (조건에 x1, y1, x2, y2는 각각 -10,000~10,000까지의 정수랬으니 제곱해도 int범위를 벗어나지 않는다) 한다.

결과적으로 O(n)의 시간내에 해결할 수 있다.

복잡하게 푸는 방법은 각 터렛에서 거리에 따른 류재명의 좌표 가능성을 죄다 구하고 일치하는 곳을 찾는 것인데, 완벽한 무한소수가 불가능한 컴퓨터에게 좋은 방법이라고 할 수는 없다. 시간이 길어지는 것 또한 있고.

#include <stdio.h>
#include <stdlib.h>

int main() {
    unsigned int testcase;

    scanf("%d", &testcase);

    int results[testcase];

    for (unsigned int i = 0; i < testcase; i++) {
        int x1, y1, r1;
        int x2, y2, r2;

        scanf("%d %d %d %d %d %d", &x1, &y1, &r1, &x2, &y2, &r2);

        if (x1 == x2 && y1 == y2 && r1 == r2) { // 일치
            results[i] = -1;
            continue;
        }

        int x_length = (x2 - x1) * (x2 - x1);
        int y_length = (y2 - y1) * (y2 - y1);
        int length = x_length + y_length;

        int min = (r2 - r1) * (r2 - r1);
        int max = (r2 + r1) * (r2 + r1);

        if (length > max || length < min) // 외부 또는 내부
            results[i] = 0;
        else if (length == max || length == min) // 외접 또는 내접
            results[i] = 1;
        else // 두 점에서 만날 때
            results[i] = 2;
    }

    for (unsigned int i = 0; i < testcase; i++)
        printf("%d\n", results[i]);

    return 0;
}