[BOJ] 1002번 - 터렛

 

 

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

1002번: 터렛

문제

조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다.

이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

한 줄에 x1, y1, r1, x2, y2, r2가 주어진다. x1, y1, x2, y2는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이고, r1, r2는 10,000보다 작거나 같은 자연수이다.

출력

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

---

1. 어떻게 풀까?

1-1) 두 원 간의 위치 관계로 나누면 되겠네요.

문제의 조건으로 두 원의 중심과 각각의 반지름을 주었으니, 이를 이용하여 문제를 해결하여야 한다. 직접 몇 가지 원을 그려보면, 두 원간의 위치 관계에 따라 두 원의 교점의 개수가 달라짐을 알 수 있다. 그런데, 어떤 경우가 있는지를 따져보아야 한다. 문제의 출력에 '위치의 개수가 무한대일 경우 -1 출력'이라고 나와있으니, 가능한 경우는 교점이 2개, 1개, 0개, 또는 무한대라고 추측해 볼 수 있다.

1-2) 그럼, 어떤 경우가 있죠?

일단, 가장 간단하게 생각해 볼 수 있는, 교점이 무한한 경우를 생각해보자.

이 경우 원의 중심이 같고, 반지름의 길이가 같은 경우를 떠올릴 수 있다. (x1 = x2, y1 = y2, r1 = r2)

또한, 이 경우 말고 교점의 개수가 무한대인 경우는 없다.

이 경우, 반지름의 길이가 다르면 어떻게 될까? 아예 교점이 발생하지 않는다. 이 경우 교점의 개수는 0이라 할 수 있다. 이를 코드로 표현하면 다음과 같이 작성할 수 있다.

if ((x1 == x2) && (y1 == y2)) {
    if (r1  == r2) {
        cout << -1 << endl;
    } else {
        cout << 0 << endl;
      } 
} 

이제, 다른 경우를 생각해보자. (두 원의 중심이 다른 경우)

두 원의 중심이 다른 경우, 다음과 같이 경우를 나눌 수 있다.

두 원의 중심간의 거리 차이를 dist라 하자.

• (두 원의 반지름의 차) < dist < (두 원의 반지름의 합) === (두 원이 2개의 교점으로 적당히 겹쳐져 있을 때)

 이 경우 교점이 2개라 할 수 있다.

• dist = (두 원의 반지름의 차) === (두 원이 내접할 때)
• dist = (두 원의 반지름의 합) === (두 원이 외접할 때)

위 두 경우 교점이 1개라 할 수 있다.

• dist < ( 두 원의 반지름의 차) === (한 원이 다른 한 원안에 있을 때)
• dist > (두 원의 반지름의 합) === (두 원이 완전히 멀리 떨어져 있을 때)

위 두 경우 교점이 0개라 할 수 있다.

 

따라서, 이 5가지 경우를 if-else 제어문으로 나타내면 다음과 같이 작성할 수 있다.

두 원의 중심간 거리는 실수(double)형이기에, 두 반지름의 합 및 차를 double형으로 변환해주었다.

double distance(int x1, int x2, int y1, int y2) {
    return sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1));
}
 
double dist = distance(x1, x2, y1, y2);
if (dist < r1+r2 && dist > abs(r1-r2)) {
    cout << 2 << endl;
} else if (dist == (double)(r1+r2) || dist == (double)abs(r1-r2)) {
    cout << 1 << endl;
} else {
    cout << 0 << endl;
}

이제, 입력단을 작성하고 코드를 완성해주면 맞았습니다! 를 받을 수 있다.

2) 최종 코드

#include <bits/stdc++.h>
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define endl "\n"
using namespace std;
 
double distance(int x1, int x2, int y1, int y2) {
    return sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1));
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int T; cin >> T;
    while (T--) {
        int x1, y1, r1, x2, y2, r2;
        cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
 
        if ((x1 == x2) && (y1 == y2)) {
            if (r1  == r2) {
                cout << -1 << endl;
            } else {
                cout << 0 << endl;
            }
        } else {
            double dist = distance(x1, x2, y1, y2);
            if (dist < r1+r2 && dist > abs(r1-r2)) {
                cout << 2 << endl;
            } else if (dist == (double)(r1+r2) || dist == (double)abs(r1-r2)) {
                cout << 1 << endl;
            } else {
                cout << 0 << endl;
            }
        }
    }
    return 0;
}

PS) 관련된 내용은 고등학교 1학년 수학 교과서의 '두 원의 위치관계에서 공부할 수 있다. :P