[BOJ] 터렛(1002) - PYTHON

두 터렛의 좌표와 목표물과 각 터렛 사이의 거리가 주어질 때, 존재 가능한 목표물의 위치 개수를 반환하는 문제이다. 즉 두 원 사이의 교차점을 의미하므로 나올 수 있는 값은 0, 1, 2, 무한대이다.

시간 복잡도: O(1)

1002번: 터렛

---

풀이과정

두 원 중심 사이의 거리와, 두 원의 크기(반지름)를 비교하며 경우를 나눈다.

distance => 두 중심 사이의 거리
r1 => 한 원의 크기
r2 => 다른 원의 크기

 

1. 두 원이 같은 경우

두 원이 같은 경우

존재 가능한 목표물의 개수가 무한대이다.

 

2. 두 원이 외접하는 경우

두 원이 외접하는 경우

교점이 1개이다. 외접하는 경우는 distance = r1 + r2인 경우다.

 

3. 두 원이 내접하는 경우

두 원이 내접하는 경우

교점이 1개이며 distance = |r1 - r2|이다.

 

4. 한 원이 다른 원 안에 있으면서 겹치지 않는 경우

한 원이 다른 원 안에 있으면서 겹치지 않는 경우

교점이 0개이며 distance < |r1 - r2|이다.

 

5. 두 원이 각각 서로의 외부에 있고, 겹치는 경우

교점이 2개이며 |r1 - r2| < distance < |r1 + r2|이다.

 

6. 두 원이 각각 서로의 외부에 있고, 겹치지 않는 경우

두 원이 각각 서로의 외부에 있고,&nbsp;겹치지 않는 경우

교점이 0개이며 distance > |r1 + r2|이다.

 

주의할 점

두 점의 거리를 구할 때,  제곱근을 사용해서 구하면 소수점이 나오는 경우 오차가 생기게 된다. (부동소수점을 사용하게 되면 오차가 발생한다.) 따라서 제곱근을 구하지 말고, 두 점 거리의 제곱을 이용해서 문제를 해결한다.

---

​코드

from math import *
 
 
def distance(x1, y1, x2, y2):
    return pow(x1 - x2, 2) + pow(y1 - y2, 2)
 
 
N = int(input())
for _ in range(N):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())
    dt = distance(x1, y1, x2, y2)
    if x1 == x2 and y1 == y2:
        if r1 == r2:
            print(-1)
        else:
            print(0)
    elif dt == pow(r1 + r2, 2) or dt == pow(r1 - r2, 2):
        print(1)
    elif pow(r1 + r2, 2) < dt < pow(r1 - r2, 2):
        print(0)
    else:
        print(2)
 

주석 추가

from math import * # pow를 사용하기 위한 모듈
 
 
def distance(x1, y1, x2, y2):  # 두 점 거리의 제곱
    return pow(x1 - x2, 2) + pow(y1 - y2, 2)
 
 
N = int(input())  # TC 개수
for _ in range(N):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())
    dt = distance(x1, y1, x2, y2)
    if x1 == x2 and y1 == y2:  # 좌표가 같을 때
        if r1 == r2:  # 거리도 같다면
            print(-1)  # 겹치는 점 개수 무한대
        else:  # 거리가 다르다면
            print(0)  # 겹치는 점 개수 0
    elif dt == pow(r1 + r2, 2) or dt == pow(r1 - r2, 2):  # 원이 내접하거나 외접할때
        print(1)
    elif pow(r1 + r2, 2) < dt < pow(r1 - r2, 2):  # 한 원이 다른 원 내부에 있거나, 겹치지 않을 떄
        print(0)
    else:  # 그 외의경우 (겹치는 점이 2개)
        print(2)

---

채점 결과

초반에 제곱근으로 문제를 풀어서 거리에 오차가 생겨 계속 틀렸다. 또 원이 한 원 내부에 있으면서 겹치지 않는 경우를 생각하지 못해서 틀렸다. 

채점 결과