데구리 블로그

문제 링크https://www.acmicpc.net/problem/1004 맞은 사람 목록을 보면 해당 풀이보다 더 간단한 풀이가 존재하는 것 같다. 어쨌든 내 경우엔 이렇게 풀었다. 좌표평면 위의 원(행성계)들이 주어지고 출발점과 도착점이 주어졌을 때, 출발점에서 도착점으로 가는 동안 원을 뚫고 가는 횟수를 최소화해야 한다.문제에서 "행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다고 가정한다."라는 조건을 주었기 때문에 쉽게 풀 수 있다. 풀이에 앞서 '점 $X$ 또는 원$X$가 원$C$에 포함된다'라는 말을 '$X$가 $C$의 경계에 걸치거나 교차하지 않으면서, $C$ 내부에 있는 상태' 라고 하겠다. 1) 출발점이나 도착점이 여러 개의 원에 포함된다면 그 원 중에서도 작은 원은 항상 큰 원에 포..

문제 링크https://www.acmicpc.net/problem/1002 두 터렛의 위치 정보와 각 터렛에서 계산한 상대편 마린과의 거리가 주어질 때 마린이 있을 수 있는 위치를 출력하는 문제다.마린이 있을 수 있는 위치는 '터렛 중심으로부터 거리가 일정한 점들의 집합'이다. 즉, 원으로 볼 수 있다. 터렛이 두 대이므로 두 원끼리 겹치는 점의 개수가 답일 것이다.두 원이 어떤 상황에서 어떻게 겹치는지 알기 위해 다음 6가지 케이스를 보면 된다. 1) 어떤 원이 다른 원에 포함되지 않으면서, 두 원이 접하지 않을 때 2) 외접할 때 3) 두 점에서 만날 때 4) 내접할 때 5) 작은 원이 큰 원 내부에 있으면서, 두 원이 접하지 않을 때 6) 두 원이 같은 원일 때 이제 주어진 원들이 어떤 상태인지 판..