[Algorithm]Baekjoon 1002번 :: 터렛

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
//#include <numeric>
 
using namespace std;
 
int t;
int ay, ax, ar, by, bx, br;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t;
 
    while (t--)
    {
        cin >> ay >> ax >> ar >> by >> bx >> br;
 
        double distance = sqrt(pow(by - ay, 2) + pow(bx - ax, 2));
        double subRadius = ar > br ? ar - br : br - ar;
 
        if (distance == 0 && subRadius == 0) // 좌표, 반지름 둘 다 같을경우
        {
            cout << -1 << endl; 
        }
        else if (distance == ar + br || distance == subRadius) // 한 점에 외접 혹은 내접하는 경우
        {
            cout << 1 << endl; 
        }
        else if (distance > subRadius && distance < br + ar) // 두 점에 걸치는경우
        {
            cout << 2 << endl;
        }
        else // 멀리 떨어져있는 경우.
        {
            cout << 0 << endl;
        }
    }
}

 

 

원의 각 교차에 관한 기하문제이다. 사실 기하문제를 많이 안풀어봤다면 이 문제가 원문제로 매칭되는지도 모를 수 있다.

 

나는 원이 충돌하는 경우만 알고있어서, 좀 더 디테일하게 알지 못했다.. 덕분에 어느 코테에서 떨어졌다.

그냥 두 원이 교차하고있는지에 대한 검사는 간단하다.

그냥 두 반지름의 합이 두 중점의 거리보다 작으면 충돌되는 것이다.

 

근데 이 문제에서는 충돌을 묻는게 아니라, 두 원의 교차점개수를 구해야하는 문제이다.

참고로 이 교차점의 좌표 y,x는 반드시 정수여야하는게 아니다.

문제에서 주어지는 인풋값이 정수인거지 류재명의 위치는 반드시 정수좌표인게 아니다.

그렇기 때문에 무한할 경우 -1을 출력하라는 문구가 있는것이다.

 

어쨌든 우리는 두 원이 한점에 외접하고있는지 내접하고있는지, 그리고 두 점에 걸쳐져있는지를 알아야 한다.

이건 공식이 있으니 참고해도되고, 위 코드의 주석을 보면 된다.

subRadius는 두 반지름의 차인데 큰값에서 작은값이 빼져있는 형태여야 한다.

 

사실 이런거 계산할때는 굳이 루트를 씌울필요 없다. 값비교일뿐이라서 계산비용이 큰 루트를 제외하고, subRadius를 제곱시켜버리면 편하다. 그러면 큰값에서 작은값을 빼든, 작은값에서 큰값을 빼든 제곱시키면 똑같으니까..

 

수정한 코드는 아래와 같다.

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
//#include <numeric>
 
using namespace std;
 
int t;
int ay, ax, ar, by, bx, br;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t;
 
    while (t--)
    {
        cin >> ay >> ax >> ar >> by >> bx >> br;
 
        int distance = pow(by - ay, 2) + pow(bx - ax, 2);
        int subRadius = pow(br - ar, 2);
        int addedRadius = pow(ar + br, 2);
 
        if (distance == 0 && subRadius == 0) // 좌표, 반지름 둘 다 같을경우
        {
            cout << -1 << endl; 
        }
        else if (distance == addedRadius || distance == subRadius) // 한 점에 외접하는 경우
        {
            cout << 1 << endl; 
        }
        else if (distance > subRadius && distance < addedRadius) // 두 점에 걸치는경우
        {
            cout << 2 << endl;
        }
        else // 멀리 떨어져있는 경우.
        {
            cout << 0 << endl;
        }
    }
}

 

 

좌표, 반지름이 둘 다 같다면 해당 원을 이루는 모든 좌표들이 류재형의 위치에 해당하기 때문에 무한하다는 것이다.

말했듯이 좌표는 실수좌표도 포함하고 있기 때문에 무한하다.