백준 1002번 파이썬 풀이: 터렛

백준 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을 출력한다.

 

문제 파악

 

초보들이 아무 생각없이 백준 문제를 1000번 A + B부터 풀다가 맞이하게 되는 고비이다.

 

백준은 난이도가 뒤죽박죽이어서 문제를 번호순으로 풀면 어려운 문제에 맞이해야 한다.

 

그런 의미에서 이 문제의 정답률은 기존의 난이도에 비해서도 상당히 낮은편에 속한다.

 

 

알고리즘 분류는 기하학으로 되있지만 수학과 기하학적인 지식이 조금 있어야 되는 문제이다.

 

이 문제를 풀기 위해선 기하학에서의 원의 정의를 짚고 넘어가야 한다.

 

원이란 한 점에서의 거리가 같은 점들의 집합 정도로 정의할 수 있다.

 

상대편 마린(류재명)이 있을 수 있는 위치의 수를 구하라는 것은

 

각 터렛의 좌표와 반지름이 주어지고 이에 대한 원의 접점을 구하라는 뜻이다.

 

두 원의 반지름을 r1, r2 두 원의 중심 사이의 거리가 d라고 할 때,

두 원의 접점이 생길 수 있는 경우의 수는 4가지가 있다.

 

1) 두 원의 접점이 무수히 많은 경우

 - (r1, r2, d가 모두 같은 경우)

 - 두 원의 중심이 같고 반지름도 같다면 점점은 무수히 많다.

 

2) 두 원의 접점이 0개인 경우

 - (r1, r2, d중에서 가장 큰수가 나머지 두 수의 합보다 큰 경우)

 - (두 원의 중심은 같지만 반지름의 길이가 다른 경우)

 - 두 원이 서로 멀리 떨어져 있는 경우 접점은 0개이다.

 - 작은 원이 큰 원안에서 접하는 부분이 없다면 접점은 0개이다.

 

3) 두 원의 접점이 1개인 경우

 - (r1, r2의 합이 d와 같은 경우 : 외접)

 - (r1, r2의 차가 d와 같은 경우 : 내접)

 - 두 원이 외접하는 경우 접점은 1개이다.

 - 두 원이 내접하는 경우 접점은 1개이다.

 

4) 두 원의 접점이 2개인 경우

 - 이 3가지 경우를 제외한 나머지 경우에 접점을 2개씩 갖는다.

 

 

코드

# 1002번

import math

T = int(input())

for _ in range(T):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())
    distance = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

    if x1 == x2 and y1 == y2:
        if r1 == r2:
            print(-1)
        else:
            print(0)
    
    else:
        if r1 > distance + r2 or r2 > distance + r1 or distance > r1 + r2:
            print(0)
        elif abs(r1 - r2) == distance or r1 + r2 == distance:
            print(1)
        else:
            print(2)

앞서 말했던 부분들을 코드로 적은것이다.

 

앞에서 자세히 설명했기 때문에 간단하게 설명해보자면

 

두 원의 중심 사이의 거리를 distance라는 변수명으로 정의하였다.

 

if else문이 너무 길어지면 가독성이 떨어질 것 같아서 원의 중심이 같을때와 그렇지 않을 때로 나누고

 

그 안에서 다시 if else문을 통해 조건을 나눴다.

 

앞에서 설명했던 경우에 맞게 마린(류재명)이 있을 수 있는 위치의 수를 출력해주면 된다.