[백준 1004][파이썬] 어린 왕자

https://www.acmicpc.net/problem/1004

1004번: 어린 왕자

조금만 생각해보면 어렵지 않게 풀 수 있다.

 

진입/이탈의 최솟값을 구하는 문제이기 때문에 출발점 혹은 도착점을 포함하고 있는 원의 개수를 세면 된다.

 

원이 점을 포함할 경우 반드시 진입 혹은 이탈을 해야하기 때문이다.

 

원이 점을 포함하고 있는지 확인을 위해서는 점과 원의 중심사이의 거리를 구하면 된다.

 

원의 중심과 점 사이의 거리가 원의 반지름보다 작으면 원이 점을 포함한다.

 

모든 원에 대하여 출발점을 포함하고 있는 원의 개수와 도착점을 포함하고  있는 원의 개수를 더하면 된다.

 

예외 사항

 

그런데 이 문제에서 예외 사항이 존재한다.

 

바로 출발점과 도착점이 같은 원에 있는 경우이다.

진입/이탈 횟수의 최소값은 0이지만 위 알고리즘대로 문제를 풀면 출발점을 포함하고 있는 원 하나, 도착점을 포함하고 있는 원 하나가 있기 때문에 2라는 오답을 낸다.

 

그래서 두 점이 하나의 원 안에 있을 때는 2를 더하게 되는데 이러한 경우에 그냥 2를 빼주고 그 값을 출력 후 바로 끝내면 된다.

 

한 가지 주의해야할 점은 반지름이 작은 원부터 조사를 해야 한다는 점이다.

 

그 이유는 다음과 같다.

작은 원부터 조사하면 먼저 도착점을 포함하고 있는 원이 하나 있으므로 1을 더한다.

 

그리고 중간 원은 아무것도 포함하지 않으므로 0을 더한다.

 

큰 원은 두 점을 포함하고 있으므로 2를 더하는데 두 점이 같은 원 안에 있으므로 2를 빼고 1을 출력하게 된다.

 

그런데 만약 가장 큰 원부터 조사를 한다고 하면 0에서 2를 더하고 2를 빼서 0이라는 오답을 출력하게 된다.

 

그래서 작은 원부터 조사를  해서 만약 두 점을 포함하고 있는 원이 있다면 2를 빼고 출력 후 종료하고 그러한 원이 없다면 끝까지 점을 포함하고 있는 원의 개수를 모두 더하여 출력한다.