[BOJ:1002] 터렛

Link : https://www.acmicpc.net/problem/1002

Note

성급하게 문제를 읽고 수도코드를 설계한 과정에서 실수가 많이 있었다. 두 원간의 교점문제라는 점은 파악했지만, 원의 교점이 생기는 경우를 분류할 때 분류과정에서 명확한 분류를 하지 못했다.

코드 중심의 최초 분류는 원의 중심인 두 점이 같을 때와 다를 때로 구분하고(원의 중심 두 점사이의 거리가 0일 때와 아닐때), 각각의 경우에 대해서 한점에서 만날 때 두점에서 만날 때, 만나지 않을 때, 겹칠 때를 나누어서 생각했다. 좋은 분류법은 아니였다. 이거는 코드 중심의 분류법에서는 좋지만 코드는 어디까지나 현실세계를 모방한 모델링이 제대로 되었을 때 의미가 있는 법이다.

다시 문제를 풀었을 때는 코드가 아닌 현실중심으로 경우를 나누어 보았다. 한 점에서 만날 때, 두 점에서 만날 때, 만나지 않을 때, 겹칠 때로 처음 부터 4가지 경우에서 경우를 분류해서 문제를 풀이하니 분류가 더 명확해 졌다. 하지만 여기서도 성급한 나머지 수도 코드 알고리즘을 점검하지 않고 바로 코드 작성으로 넘어가면서 반례를 생각하지 못했다. 반례가 발생한 코드는, 원이 두 점에서 만나는 경우에서 생겼는데, 두 중심사이의 거리를 d, 각각의 원의 반지름을 r1, r2라고 할때 'd < r1 + r2'인 경우만 두 점에서 만난다고 생각했다. 이 경우만 생각하면 반례가 생긴다. 두 원의 중심 사이들 끼리의 거리가 너무 가까워서 r1 + r2보다 당연히 작은 경우이다.

조금 더 풀어서 생각하면 두 원이 외접하는 두 원이 있을 때 한 원을 계속 다른 원의 중심에 가깝도록 살짝 이동 시키면 두 점에서 만나게 되는데 이때 계속 가깝게 이동하면 내접하는 경우가 생기고, 더 가까워지면 만나지 않는 경우가 생기게 된다. 즉, 외접하는 경우에서 원을 이동 시킬때, 두 원의 중심사이의 거리가 필요 이상으로 가까워져서 한 점에서 내접하는 경우까지 오기 전까지 두 원의 중심사이의 거리를 좁힐 때만 원은 두 점에서 만나게 된다.

아래는 두 원이 놓일 수 있는 경우를 나타낸 그림이다.

원이 겹치는 경우 d = 0, r1 = r2

한 점에서 만나는 경우(내접, 외접) , d = r1 + r2 or d =r2-r1

두 점에서 만나는 경우 r2-r1 < d< r1 + r2

만나지 않는 경우는 위의 경우를 제외한 모든 경우 만나지 않는다.

이렇게 두 점에서 만나는 경우를 범위를 나누어서 생각 하지 못했다. 내가 너무나 자주하는 실수이다. 문제를 정확히 읽고 코드를 세운 다음에도 다시 한 번 코드를 점검할 필요가 있다. 성급하지 말고 문제해결의 알고리즘이 문제의 모든 경우를 해결해줄 알고리즘인지 항상 검증하는 과정이 필요하다. 이렇게 알고리즘을 풀 때는 비판적 사고를 하면서 반례가 없을지 충분히 생각해 보아야한다

Code

import sys

input = sys.stdin.readline

t = int(input())

for _ in range(t):
    x1,y1,r1,x2,y2,r2 = map(int,input().split())
    two_p_dis = ((x1-x2)**2 + (y1-y2)**2)**(1/2)
    if two_p_dis == 0:
        if r1 == r2:
            print(-1)
        else:
            print(0)
    else:
        if two_p_dis == r1 + r2 or two_p_dis == abs(r2-r1):
            print(1)
        elif two_p_dis < r1 + r2 and (abs(r2-r1) < two_p_dis):
            print(2)
        else:
            print(0)