[백준 알고리즘] 1002 터렛

문제:    

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

1002번: 터렛

풀이방법:    

우선 문제를 읽고 원을 떠올려야 한다. (조규현을 A, 백승환을 B 그리고, 류재명이 X라고 하겠다.)

A와 B가 있는 곳과 X와의 거리만을 알고 있기 때문에 A가 있는 곳으로부터 거리 X를 선으로 그으면 하나의 원이 생기고 , B도 마찬가지로 그으면 새로운 원이 생긴다. 그리고 그 원의 접점들이 바로 X가 있을 수 있는 곳 !!

 

원을 그어서 생각을 해보면 우선 크게 중심이 같은 경우와 다른 경우로 나뉜다. 

아래의 그림을 보면 중심이 같을 경우에는 0과 -1,

중심이 다를 경우에는 0,1,2의 결과가 도출될 수 있음을 알 수 있다.

 

 

 

 

작성한 코드는 다음과 같다.

#include <iostream>
#include <math.h>
using namespace std;

int main() {
    int count;
    cin >> count;
    for(int i = 0;i < count ; i++){
        int x1, y1, r1, x2, y2, r2;
        cin >> x1>> y1>> r1>> x2>> y2>> r2;
        
        int d = pow(x1-x2,2) + pow(y1-y2,2);
        int R1 = pow(r1 - r2,2);
        int R2 = pow(r1 + r2,2);
        
        //중심이 같을 때
        if(d == 0){
            if( R1 == 0 ) {
                cout << "-1" <<"\n";
            }else{
                cout << "0" <<"\n";
            }
            //중심이 다를 때
        }else if( d == R1 || d == R2) {
            cout << "1" <<"\n";
        }else if( d > R2 || d < R1) {
            cout << "0" <<"\n";
        }else{
            cout << "2" <<"\n";
        }
    }
    return 0;
}

성공한 사진!  

 

추가 ) 

제대로 코드를 작성한 것 같았는데 계속 틀렸습니다가 떴다.. 그 이유는 거리 d의 제곱이 아닌 거리 d와 R1(r1 - r2), R2(r1 + r2)로 비교를 하고 있었던 것이다.. 문제에서 정수로 제한을 둔 이유가 있지.. 거리 d를 구하게 되면 제곱근을 사용해야 하는데 그럴 경우, 소수가 나오게 된다. 그러면 이후 R2,R1과의 비교에서 ㅎㅎ.. 문제가 있을 수 있ㄷㅏ... 

나같은 잘못을 저지르는 사람이 없길 바란다..

 

다음은 1002관련해서 어떤 분이 맛나게 정리해둔 글이다. 잘 모르겠는 사람들이 참고하면 도움이 될 듯 싶어 같이 남긴다 !

https://www.acmicpc.net/board/view/38854

글 읽기 - ★☆★☆★ 터렛 FAQ ★☆★☆★ 터렛 FAQ ★☆★☆★

 

3번 :

"두 중심 사이 거리를 R이라고 할 때, 무턱대고 R == r1 + r2인지 검사하는 것은 매우 위험합니다. 

조금의 오차라도 생기면 두 실수는 같지 않게 되기 때문입니다. 간단한 예시로, 0.1 + 0.2 == 0.3은 참이 아닙니다.

마찬가지로 r1, r2 등을 float, double 등의 자료형으로 저장하면 위험합니다."

 

--> 실제로 0.1+0.2를 출력하면 0.3이 아닌 0.300000000004 가 나온다. 

https://stackoverflow.com/questions/588004/is-floating-point-math-broken

Is floating point math broken?