백준 1002번 터렛 _ C++, python 두가지 풀이.

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

1002번: 터렛

일단 문제가 너무 귀엽다.. 존재감이 없어서 인구수는 잡아먹지 않는다니..ㅋㅋㅋㅋ
각설하고, 바로 문제를 보자!

이 문제는 쉽게 두 사람(조씨와 백씨)의 위치와 적으로부터의 거리가 주어졌을 때 적이 있을 수 있는 위치의 갯수를 반환하는 문제이다.

그러면 이렇게 생각할 수 있겠다.
한 사람의 위치(x,y)와 적으로부터의 거리(r)가 주어진다면 적이 있을 수 있는 위치는 그 사람(x,y)로부터 반지름 r로 그려진 원 위일 것이다.
그렇다면 두 사람의 위치와 각각의 적으로부터의 거리가 주어진다면? 적이 있을 수 있는 위치는 그려지는 두 원의 교점일 것이다.

이 개념을 이용하면 이 문제는 두 원의 좌표와 두 원의 반지름이 주어졌을 때 교점의 갯수를 구하는 문제로 재정의 될 수 있다.
그림으로 설명하면 더 쉽겠지만, 귀찮은 관계로 글로 해결책을 설명하겠다.

두 원의 중심이 동일하고, 반지름이 같다면 적이 존재할 수 있는 좌표는 무한대이다 -> -1 리턴
두 원의 반지름의 합이 두 원의 중심사이의 거리라면 외접, 두 원의 반지름의 차가 두 원의 중심사이의 거리라면 내접한다 -> 1리턴
두 원의 반지름의 합이 두 원의 중심사이의 거리보다 크고, 두 원의 반지름의 차가 두 원의 중심사이의 거리보다 작다면 두개의 교점 -> 2리턴
그 외에는 교점이 없다. -> 0리턴

이를 파이썬으로 그대로 알고리즘을 짜보면 다음과 같다.

import math
num = int(input())
results = []

for i in range(num):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())
    d = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) # 두 원의 중심 사이의 거리
    if x1 == x2 and y1 == y2 and r1 == r2: results.append(-1) # 교점이 무한대
    elif abs(r1 - r2) < d and r1 + r2 > d: results.append(2) # 교점이 두 개인 경우
    elif abs(r1 - r2) == d or r1 + r2 == d: results.append(1) # 접하는 경우
    else: results.append(0) # 교점이 없음

for result in results:
    print(result)

이렇게 간단하게 짜면 될 것을 한번 C++에서는 클래스의 개념으로 마치 말하는 것처럼 짜보자.
말하고자 하는 것은 아래와 같다.

조씨라는 터렛직원이 있고 백씨라는 터렛직원이 있고 그들의 좌표와 적으로부터의 거리가 있다면
조씨와 백씨의 마린 가능 위치는 몇이다!

이 때 클래스의 정보은닉을 지키고자 굳이 get()함수를 구현했다.

#include <iostream>
#include <cmath>
using namespace std;

class Turret{
private:
    int x, y;
    int r;
public:
    Turret(int x, int y, int r): x(x), y(y), r(r) {}
    int getX() {return x;}
    int getY() {return y;}
    int getR() {return r;}
    int marine_detection(Turret others);
};

int main(){
    int num;
    cin >> num;
    for (int i=0; i<num; i++){
        int x,y,r,_x,_y,_r;
        cin >> x >> y >> r >> _x >> _y >> _r;
        Turret Jo(x,y,r); //조규현의 터렛 생성
        Turret Baek(_x,_y,_r); //백승환의 터렛 생성
        cout << Jo.marine_detection(Baek) << '\n'; //두 터렛의 교점 출력
    }
    return 0;
}

int Turret::marine_detection(Turret others){
    int _x = others.getX();
    int _y = others.getY();
    int _r = others.getR();
    double d = sqrt(pow(x-_x,2)+pow(y-_y,2)); //두 원점 사이를 계산, 이때 자료형이 double임을 조심하자.
    if (x==_x && y==_y){
        if(r==_r) {return -1;} // 두 원의 중심이 동일하고, 반지름이 같다면 류재명이 존재할 수 있는 좌표의 개수는 무한대
        else {return 0;}}
    else if ((r+_r)>d && abs(r-_r)<d){return 2;} //교점이 두 개인 경우
    else if ((r+_r)==d || abs(r-_r)==d){return 1;} //교점이 한 개인 경우
    else {return 0;}
}

걸린 메모리와 시간을 비교해보면 다음과 같다.

끝!