[백준] 1002_터렛 파이썬 (원의 내접과 외접 활용)

---

상당히 고전했던 문제다.

다 풀었다고 생각했는데 틀리고, 수정했는데 또 틀리는 그런 형태의 문제

구현 자체에 대한 문제도 있었지만, 

아무래도 문제 자체가 수학, 그중에서도 기하학에 대한 개념이 있어야 했기에 더 어려움을 가졌던 것 같다.

 

우선 이 문제를 알기 위해서는 반드시 알아야 할 것이 "원의 내접과 외접, 그리고 위치 관계"에 대한 부분이다.

자세한 부분은 일단 다음 사이트를 참조하는 것이 최고다.

 

공부 참조 출처: https://mathbang.net/101

두 원의 위치관계, 내접, 외접

 

---

위의 내용을 알기 전에는 다음과 같이 코딩을 하였다.

# 시도1
test_case = int(input())  # 테스트 케이스 갯수
for i in range(test_case):
    x1, y1, r1, x2, y2, r2 = list(map(int, input().split()))  # 조규현 좌표(x1, y1)과 백승환 좌표(x2, y2)와 류재명과의 거리 r1, r2
    distance = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
    if distance == 0:
        if r1 != r2:  # 류가 있을 수 있는 위치가 존재하지 않는다.
            print(0)
        else:  # 류가 있을 수 있는 위치는 r1(=r2)를 반지름으로 가진 원의 위치 중 어디든 가능하다.
            print(-1)
    else:
        if (r1+r2) == distance:  # r1과r2가 만나는 지점 1군데에서 류가 있을 수 있다.
            print(1)
        elif (r1+r2) > distance:  # r1+r2가 더 크다면 distance 직선기준으로 아래 위로 총 2군데 발생할 수 있다.
            print(2)
        else:
            pass

---

하지만 계속 백준에서 틀렸다고 나왔고, 그래서 결국 기억을 짜내서 원의 내접과 외접이 생각나서 인터넷 검색을 통해서 조건을 알게 되었다.

 

조건을 정리하자면 다음과 같다.

계산한 거리는 반지름으로 r1, r2(r1 > r2)를 가지고, 두 중심간의 거리를 d라고 가정할 때
두 점에서 만나는 경우
d != 0 and r1 - r2 < d < r1 + r2
한 점에서 만나는 경우
d != 0 and { r1+r2 = d (외접) r1-r2 = d(내접)}
한 점에서도 만나지 않을 경우
d = 0 and r1 - r2 != 0
d != 0 and r1 + r2 > d
무수히 많은 점에서 만날 경우
d = 0 and r1 - r2 = 0

 

이런 조건들을 통해서 다시 만든 코드는 다음과 같다.

# 시도2
test_case = int(input())  # 테스트 케이스 갯수
for i in range(test_case):
    x1, y1, r1, x2, y2, r2 = list(map(int, input().split()))  # 조규현 좌표(x1, y1)과 백승환 좌표(x2, y2)와 류재명과의 거리 r1, r2
    distance = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
    if distance == 0:
        if r1 != r2:  # 류가 있을 수 있는 위치가 존재하지 않는다.
            print(0)
        else:  # 류가 있을 수 있는 위치는 r1(=r2)를 반지름으로 가진 원의 위치 중 어디든 가능하다.
            print(-1)
    else:
        if (r1+r2) == distance or abs(r1-r2) == distance:  # r1과r2가 만나는 지점 1군데에서 류가 있을 수 있다.
            print(1)
        elif (r1+r2) > distance and abs(r1-r2) < distance:  # r1+r2가 더 크다면 distance 직선기준으로 아래 위로 총 2군데 발생할 수 있다.
            print(2)
        else:
            pass

---

문제는 위의 코드도 틀렸다는 점이다.

틀린 이유는 else문 내의 else문 때문이다.

else문의 경우 pass가 아닌 0을 출력해야 하기 때문이다. 이유는, if-elif를 통해서 찾을 수 있는 경우들을 제외하면 점을 가질 수 없기 때문이고, 점이 없을 때는 0을 출력해야 하기 때문이다.

(이 틀린 부분을 찾기 위해서 상당히 오랜 시간이 걸렸다....)

 

결론적으로 제대로 된 코드는 다음과 같다!!!

test_case = int(input())  # 테스트 케이스 갯수
 
for i in range(test_case):
    x1, y1, r1, x2, y2, r2 = list(map(int, input().split()))  # 조규현 좌표(x1, y1)과 백승환 좌표(x2, y2)와 류재명과의 거리 r1, r2
    distance = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
    if distance == 0:
        if r1 != r2:  # 류가 있을 수 있는 위치가 존재하지 않는다.
            print(0)
        else:  # 류가 있을 수 있는 위치는 r1(=r2)를 반지름으로 가진 원의 위치 중 어디든 가능하다.
            print(-1)
    else:
        if (r1+r2) == distance or abs(r1-r2) == distance:  # r1과r2가 만나는 지점 1군데에서 류가 있을 수 있다.
            print(1)
        elif (r1+r2) > distance and abs(r1-r2) < distance:  # r1+r2가 더 크다면 distance 직선기준으로 아래 위로 총 2군데 발생할 수 있다.
            print(2)
        else:
            print(0)
 

---

상당히 오래 걸린 문제이고, 결국에는 원의 내접과 외접에 대해서 알아야 했던 문제이다.

보아하니 원의 내접과 외접은 중학교 수준의 문제라는 것 같다... 

 

 

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

1002번: 터렛