-
[알고리즘 문제 풀이][기하학] 백준 1002번 - 터렛자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 2. 12. 20:05
백준 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
'자료구조&알고리즘 > 알고리즘 - 대회 알고리즘' 카테고리의 다른 글
[알고리즘 문제 풀이][기하학] 백준 3053번 - 택시 기하학 (0) 2022.02.15 [알고리즘 문제 풀이][완전탐색] 백준 12784번 - 인하니카 공화국 (0) 2022.02.13 [알고리즘 문제 풀이][슬라이딩윈도우] 백준 16440번 - 제이크와 케이크 (0) 2022.01.28 [알고리즘 문제 풀이][조합] 백준 17205번 - 진우의 비밀번호 (0) 2022.01.19 [알고리즘 문제 풀이][슬라이딩 윈도우] 백준 15961번 - 회전 초밥 (0) 2022.01.05 댓글