알고리즘 & 코딩테스트
[백준] 1002번 터렛
Haksae
2022. 3. 5. 17:01
⛏ 문제 파악
- 두 개의 터렛의 좌표가 주어지고, 각 터렛에서 타깃과의 거리가 주어지고, 타깃이 위치할 수 있는 경우의 수를 출력하는 문제
- 타깃이 이을 수 있는 위치의 수를 구하라는 것은, 각 테럿의 좌표와 반지름을 가지고 원의 접점을 구하라는 뜻이다.
- 1) 이것을 위해서는 먼저 두 터렛 간의 거리가 필요한데, 이는 원의 방정식을 이용해서 구하면 된다.
- 원의 방정식은 다음과 같다. (피타고라스 정의)
- 2) 그리고 각 터렛의 좌표와 반지름, 두 터렛 간의 거리를 가지고, 원의 접점을 구하면 된다. (타깃과의 위치를 원의 반지름이라 생각하고 원을 그려서 접점을 구한다고 생각하면 된다.)
원의 접점을 구하는 경우의 수는 4가지이다.
아래 그림에서 각 터렛의 반지름을 r1, r2, r은 터렛 간의 거리이다.
(1) 두 원이 일치하는 경우
- r1, r2가 같고, d가 0인 경우
- 두 원이 일치하므로 접점이 무수히 많다.
- 해당 문제에서 이 경우에는 -1을 출력한다.
(2) 두 원이 한 점에서 만나는 경우 (외접, 내접)
- r1, r2 합이 r과 같은 경우 : 외접
- r1, r2의 차가 r과 같은 경우 : 내접
- 두 원이 내접하거나 외접하면 접점은 1이므로, 1이 출력된다.
(3) 두 원이 만나지 않는 경우
- r, r1, r2 중 가장 긴 값이 나머지 두 값의 합보다 큰 경우에는, 원이 멀리 떨어져있거나, 작은 원이 큰 원 안에 접하는 부분이 없이 있는 경우이다. 해당 경우에는 두 원이 만나지 않는다.
- 접점이 없으므로 0을 출력한다.
(4) 두 원이 두 점에서 만나는 경우
- 두 원의 거리가 반지름의 차보다 크고 합보다 작을 때 두 원이 두 점에서 만난다.
- |r1-r2| < r < r1+r2
- 해당 경우에는 2를 출력한다.
👉🏻 답안
- 위의 방법들을 코드로 만들면 다음과 같다.
import math
T = int(input())
for _ in range(T):
x1, y1, r1, x2, y2, r2 = map(int, input().split())
distance = math.sqrt((x1-x2)**2 + (y1-y2)**2) #거리를 구하는 코드
if distance == 0 and r1 == r2: #두 원이 일치하는 경우
print(-1)
elif abs(r1-r2) == distance or r1 + r2 == distance: #두 원이 한 점에서 만나는 경우
print(1)
elif abs(r1-r2) < distance < (r1 + r2): # 두 원이 두 점에서 만나는 경우
print(2)
else: # 두 원이 만나지 않는 경우
print(0)
📑 간단한 설명
- distance가 각 테럿 간의 거리이고,
- math.sqrt((x1-x2)**2 + (y1-y2)**2) 는 원의 방정식으로 그 거리를 구하는 코드다.
- 그 뒤로는 두 원의 경우의 수이다.