[백준 알고리즘: python 3] #1004 - 어린 왕자

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

 

1004번에는 어린 왕자의 여행과 연관하여 문제가 소개되어 있습니다. 어린 왕자가 출발지로부터 도착지까지 행성계 사이를 여행하는데, 제시된 행성계의 경계를 최소 몇번 진입/이탈 할 것인지 구하는 문제입니다. 입력은 어린 왕자의 출발지, 도착지의 좌표와 행성계의 수, 그리고 각 행성계의 중심 좌표와 반지름이 주어집니다.

 

문제의 그림에서는 총 3번의 진입과 이탈이 발생하게 됩니다.

1004번 문제의 그림

Hint!

문제는, 언제 진입/이탈이 불가피한 지를 파악하는 것입니다. 공책에 아무데나 원을 그리고 출발지와 도착점을 찍어보세요. 그림은 아래 네가지 상황 중 하나일 것입니다.

 

1. 출발지와 도착지가 모두 원이 포함될 때,
2. 출발지가 원에 포함되고, 도착지는 포함되지 않을 때.
3. 출발지가 원에 포함되지 않고, 도착지는 포함될 때.
4. 출발지와 도착지가 모두 원에 포함되지 않을 때.

그러고 나서, 진입/이탈을 최대한 하지 않는 방향으로 선을 그어보시면, 2번과 3번의 경우에만 원의 경계를 반드시 진입/이탈해야 한다는 것을 알 수가 있습니다. 즉, 출발지나 도착지 중 한 점만 포함하는 원의 개수를 구하는 문제입니다. 1번의 경우에는 원의 경계에 갈 필요없이 직선을 그으시면 되고, 4번의 경우에는 원을 피해 선을 그리면 피할 수 있을겁니다. 이제 위의 그림을 다시 보면 이해가 쉬워집니다. 

 

즉, 입력으로 주어진 어린왕자의 출발지 좌표만을 포함하는 행성계(원)와 도착지 좌표만을 포함하는 행성계의 개수를 구해 더하면 됩니다. 두 점을 모두 포함하는 행성계는 제외해야 한다는 점을 잊지 마세요! 여기서 점이 원에 포함하는지 확인하려면, 원의 중심과 점 사이의 거리가 반지름보다 큰지 작은지를 파악해야합니다. 거리가 반지름보다 크면, 원 밖에 있는 점이고 작으면 원 안에 있는 점이겠죠? 이러한 생각으로 아래와 같은 코드로 풀이하였습니다.

 

import math
cases = int(input())
results = []

for case in range(cases):
    count = 0
    x1, y1, x2, y2 = map(int, input().split())
    ps = int(input())
    planets = []
    for p in range(ps):
        px, py, pr = map(int, input().split())
        # 출발지와 원의 중심 사이의 거리
        d1 = math.sqrt((x1 - px) ** 2 + (y1 - py) ** 2)
        # 도착지와 원의 중심 사이의 거리
        d2 = math.sqrt((x2 - px) ** 2 + (y2 - py) ** 2)
        # 출발지 또는 도착지가 중심 사이의 거리보다 작다면 진입/이탈
        if d1 < pr or d2 < pr:
        	# 이지만 둘 다 포함하는 경우는 패스
            if d1 < pr and d2 < pr: pass
            else: count += 1
    results.append(count)

for result in results:
    print(result)