백준 알고리즘 1002번: 터렛 C언어

문제 출처: https://www.acmicpc.net/problem/1002

1002번: 터렛

1. 코드

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

int main(void)
{
    int t, x1, y1, r1, x2, y2, r2, result;
    double distanse, subtract;    //거리, 뺄셈
    scanf("%d", &t);
    
    while(t--)
    {
        scanf("%d %d %d %d %d %d", &x1, &y1, &r1, &x2, &y2, &r2);
        distanse = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));    //(x1, y1)와 (x2, y2)의 거리
        subtract = r1 > r2 ? r1 - r2 : r2 - r1;
        
        if(distanse == 0 && r1 == r2) result = -1;    //두 원이 완전히 일치하는 경우
        else if(distanse < r1 + r2 && (subtract < distanse)) result = 2;    //두 원의 교점이 2개일 경우
        else if(distanse == r1 + r2 || distanse == subtract) result = 1;    //두 원의 교점이 1개일 경우
        else result = 0;    //두 원의 교점이 없을 경우
        
        printf("%d\n", result);
    }
}

2. 문제 해결 방식

조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.

제일 중요한 문제의 요소들이 다 모여있다. 이것들을 조금 정리해보면 조규현의 좌표(x1, y1)인데 류재명과의 거리는 r1이다. 그렇다면 조규현과 류재명이 있을 만한 위치는 마치 원처럼 보일 것이다. 원처럼 보인다는 것이 어떠한 말인지 지금 설명하겠다. 원의 정의는 한 점을 중심으로 같은 거리 떨어진 점들의 집합을 원이라고 하는데 마치 조규현과 류재명의 관계처럼 보인다.

 

 

A_1이 조규현의 좌표이고 류재명과의 거리가 13이라고 할 때 과연 류재명은 어디에 있을지 맞춰보자. A, B, C...? 맞다. 전부 존재할 수 있다. 그렇다면 류재명의 위치를 어떻게 특정하는지 고민해봐야 한다. 그런데 문제를 보면 백승환의 좌표가 주어지고 류재명과의 거리인 r2가 주어진다고 한다. 그러면 백승환과 조규현을 중심으로 류재명의 거리만큼 원을 그린 다음 겹치는 부분이 류재명의 위치이다.

그렇다면 이 문제는 두 원의 교점을 찾는 문제가 되어버린다. 그렇다면 원의 교점을 찾아야 하는데 우선 두 원의 교점의 개수가 몇 개씩 존재하는지 생각해보자. 우선 무수히 많은 경우와 2개일 경우 1개일 경우 그리고 없는 경우이다.

무수히 많은 경우는 조규현의 좌표(x1, y1)와 백승환의 좌표(x2, y2)가 같아야 한다. 또한 각각의 류재명의 거리인 t1과 t2가 같아야 원의 모양이 완전히 동일해진다. 

만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

완전히 동일해질 때는 류재명의 있을 위치의 개수가 무한대이기 때문에 -1을 출력하게 한다. 그렇다면 이것을 공식화하면 다음과 같다.

x1 = x2, y1 = y2 , r1 = r2 이 조건이 성립되었을 때 두 원의 교점의 개수는 무한대이다.

그리고 교점이 2개일 경우인데 그림은 다음과 같다.

 

 

두 원이 겹치기 위해서는 r1의 길이와 r2의 길이가 d보다 길어야 두 개의 교점이 생긴다. 그런데 이 조건만 있으면 안 되고 다른 추가적인 조건 하나가 더 필요하다.

 

 

그림을 보면 r1 + r2의 값이 d보다 크다. 하지만 두 원의 교점이 존재하지 않는다. 그렇기에 r2과 r1의 차이가 d보다 더 짧아야 두 개의 교점이 생긴다.

r2 - r1 < d < r1 + r2 (단, r1 < r2 일 경우) 두 원의 교점은 2개 존재한다.

그리고 교점의 개수가 1개일 경우는 2가지가 있다. 일단 첫 번째 경우는 다음과 같다.

 

 

첫 번째 경우는 내접했을 때의 경우인데 그림을 보면 r2 - r1의 값이 d라는 것을 알 수 있다. 다음은 두 번째 경우이다.

 

 

지금은 외접을 했을 경우이다. 외접을 하기 위해서는 r1 + r2의 값이 d와 동일해야 한다.

r2 - r1 = r1 + r2 = d (단, r1 < r2 일 경우) 두 원의 교점은 1개 존재한다.

0개일 경우는 else 문을 이용하여 처리할 생각이기에 구하지 않겠다. 그리고 계속해서 나온 d는 조규현과 백승환의 거리이므로 두 점 사이의 거리는 구하는 공식을 이용하여 해결하겠다.

√((x2 - x1)^2 + (y2 - y1)^2) = 두 점 사이의 거리

그러면 이제 문제에 필요한 정보들을 수집이 끝이 났으니 이제 코딩을 시작해보자. 그런데 이번에는 루트의 기호를 사용하기 때문에 math.h라는 헤더 파일을 이용해보자. math.h는 수학적인 연산을 위한 함수들이 다양하게 적용할 수 있다. 그곳에서 pow문과 sqrt문을 사용하겠다.

double pow ( double x, double y ); // x^y를 구한다.
double sqrt ( double x ); // √x를 구한다.

이제 이 공식들과 함수들을 이용하여 풀어내면 해결할 수 있다.

4. 느낀 점

처음에는 어떠한 문제인지 전혀 감이 잡히지 않았는데 계속해서 문제를 보다 보니 원과 같은 모양이 나오는 것을 보고 두 원의 교점의 개수를 구하는 문제라는 것을 깨달아도 문제를 해결할 수 없었다. 그래서 두 원의 교점 관계에 대해 검색해가며 알아내었다.

그리고 math.h 헤더 파일은 오랜만에 써서 뭔가 생소한 느낌이었다.