[알고리즘 문제 풀이][기하학] 백준 1002번 - 터렛

백준 1002번 터렛 문제입니다.

(기하학 - 원의 교점의 개수)

 

- 문제 설명: https://www.acmicpc.net/problem/1002

- 문제 풀이:

 

본 문제는 현재 위치, 적까지의 거리가 주어집니다. 그런데 한 명의 정보가 아니라 2명의 정보가 주어집니다. 문제를 풀기 위해서는 두 명의 정보가 동시에 가리키는 위치를 찾아야합니다. 하나의 거리가 r1 으로 주어졌을 때 가능한 좌표는 r1 만큼 떨어진 모든 곳이므로 원을 하나 그리게 됩니다. 또 다른 한명이 가리키는 거리가 r2 로 주어지면 가능한 좌표는 r2 만큼 떨어진 원형이 됩니다. 두 명이 동시에 가리키는 좌표는 겹치는 한 곳일 수도 있고, 원 두 개가 겹치는 경우를 생각하면 2 곳일 수도 있습니다.

 

원의 교점의 개수를 구하기 위해 구분하는 종류는 아래와 같습니다.

원과 원의 위치 관계

[그림 출처] https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=junhyuk7272&logNo=221139170814

 

위의 그림에는 구별되어서 나와 있지 않지만 문제에서 언급한 한 가지 경우가 또 있습니다. 두 사람의 좌표도 적과의 거리도 완전히 동일한 경우입니다. 그러면 가능한 모든 점이 무한히 많아지는데, 이런 경우에는 -1 을 출력하라고 안내되어있습니다. 위의 그림과 이 경우를 고려하여 그대로 코드를 작성하면 됩니다.

 

- 코드: 

for _ in range(int(input())):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())
    dist = (x1-x2)**2 + (y1-y2)**2
    rsum = (r1+r2)**2
    rsub = (r1-r2)**2

    if dist > rsum:
        print(0)
    elif dist == rsum:
        print(1)
    elif rsub < dist < rsum:
        print(2)
    elif dist == rsub:
        if dist == 0:
            print(-1)
        else:
            print(1)
    elif dist < rsub:
        print(0)

 

- 실수 포인트 & 반례:

1. 완전히 좌표와 거리가 동일한 경우 (문제에 예제로 추가가 필요할 것 같습니다)

입력
1
1 2 3 1 2 3
정답
-1

 

2. 실수형 연산으로는 오차가 생겨서 오답이 생김 (제곱으로 푸는 것을 권장)

https://www.acmicpc.net/board/view/80483

입력)
4
-1 8 10 -1 0 10
-6 3 9 -1 7 6
-2 3 8 1 2 5
2 9 6 10 9 10

정답)
2
2
2
2

https://www.acmicpc.net/board/view/79828

입력)
2
0 0 3 1 2 1
0 0 1 1 1 1

정답)
2
2

 

3. 그 외 다양한 반례들

https://www.acmicpc.net/board/view/81251

입력)
1
-30 40 50 -3 4 5

정답)
1

https://www.acmicpc.net/board/view/80940

입력
1
1 1 3 2 2 1

정답)
0