백준 1002번 터렛

1002번: 터렛 (acmicpc.net)

1002번: 터렛

 

 

문제 요약: 조규환의 좌표는 x1, y1 백승환의 좌표는 x2, y2 조규현이 계산한 류재명과의 거리는 r1 백승환이 계산한 류재명과의 거리는 r2이다. 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성해라. 단, x1, y1, x2, y2는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이고, r1, r2는 10,000보다 작거나 같은 자연수이다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. 

 

 

 

문제 풀이: 이 문제를 접했을 때, 이게 무슨 문제지..? 하고 몇 번을 읽어본 것 같다. 처음에는 두 점 사이의 거리와 관련된 문제로 알고 접근했지만, 아니었다. 두 원점 사이의 거리와 관련된 문제였고 접근법을 알면서도 여러 개의 케이스 때문에 조금 헷갈려하면서 풀었던 것 같다. 그림을 그리면서 이해하면 쉽지만, 내가 그림을 잘 못 그려서 아쉬울 뿐이다. 

먼저 이 문제가 왜 두 원점 사이의 거리와 관련된 문제냐면 만약 x1이 0, y1이 0, r1이 13이라면 류재명은 조규환의 위치를 기준으로 1사분면에 거리가 13이 되는 지점에 있을 수도 있고, 2 사분면, 3 사분면, 4 사분면 상관없이 거리만 13이면 어디에든 존재할 수 있다. 이 류재명이 존재할 수 있는 무수한 점들을 이어 보면 당연히 원이 되고, 조규환이 있는 지점은 원점이 된다는 사실을 알 수 있다. 이제부터는 그림을 그리면서 접근하면 더 쉽다. 류재명이 위치의 개수는 r1과 r2가 두 개의 교점을 이룰 때 2개, 외접원과 내접원일 때 1개, 동심원일 때 무한개, 교점을 이루지 않을 때 0개로 4개의 케이스가 존재한다. 교점이 2개일 케이스가 조금 헷갈릴 것 같은데 그림을 그려서 설명해보겠다. 

우선 r2와 r1의 합이 d(원점 사이의 거리)보다 작다면 교점이 생기지 않는다. 하지만 반지름의 합이 d보다 크지만 교점이 없는 경우가 있는데 두 반지름의 차이가 두 원점 사이의 거리보다 클 때이다. 그렇기 떄문에 교점이 2개가 생기는 경우는 두 반지름의 합이 두 원점 사이의 거리보다 커야 하고, 차이가 두 원점 사이의 거리보다 작아야 한다. 

 

 

 

 

http://colorscripter.com/s/fShMx43

공유된 코드 - Color Scripter