백준 - 1002 터렛

알고리즘을 공부하기 시작하고 처음 2시간 걸린 알고리즘 문제입니다.

 

알고리즘 공부 2일차. 삼성 SW Expert 강의와 백준을 병행하니 시간이 너무 부족하고 체력도 너무 모자란 느낌이 듭니다 ㅡ.ㅡ

 

체력이 충분해야 공부도 잘한다고 하던데 큰일이네요. 아무튼 사족은 여기까지 하고! 문제 얘기를 하겠습니다.

 

터렛 문제는 2개의 터렛이 있고 각 터렛의 2차원 좌표와 각 터렛에서의 목표물까지의 거리를 주고 목표물이 존재할 수 있는 경우의 수를 구하는 문제입니다!

 

코드부터 보시죠!

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

int main(int argc, char** argv)
{
    int x1, x2, y1, y2, r1, r2, T;
    double d;
    scanf("%d", &T);
    
    for(int t = 1; t <= T; t++) 
    {
        scanf("%d %d %d %d %d %d", &x1, &y1, &r1, &x2, &y2, &r2);
        d = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
        if(d == 0)
        {
            if(r1 == r2) {
                // 동치
                printf("-1\n");
            }
            else {
                // 외부에 혹은 내부에
                printf("0\n");
            } 
            continue;
        } 
        else if((d > (r1 + r2)) || d < abs(r1 - r2))
        {
            // 외부 혹은 내부
            printf("0\n");
        }
        else if(d == (r1 + r2) || d == abs(r1 - r2)) 
            // 내접 혹은 외접
            printf("1\n");

            // 만남
        else if(d < (r1 + r2) || d > abs(r1 - r2)) printf("2\n");
        else printf("0\n");
    }
}

 

터렛 문제는 기하 알고리즘 문제라고 합니다.

기하학을 이용해서 푸는 문제라는 소리죠. 

감이 오시겠지만 터렛 문제는 두 원의 교점 갯수를 찾는 문제입니다.

 

기하학의 원의 교점을 구하는 공식을 참고하여 모든 경우의 수를 판별하면 되었습니다.