[수학/기하학] 백준 1004 어린 왕자 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1004번: 어린 왕자

 

 

 

2. 문제 풀이

 출발지(x1, y1)부터 어린왕자가 도착지(x2, y2)까지 행성 여행을 합니다. N개의 행성들이 주어지며, 최대한 행성들을 지나치지 않고 가야 합니다.

 

 

  중간에 아무리 가로막고 있어도, 우회해서 갈 수 있습니다. 따라서, 출발지와 도착지를 감싸는 행성계만 찾으면 됩니다. 

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
T = int(input())
for _ in range(T):
    x1, y1, x2, y2 = map(int, input().split())
    res = 0  # 거치는 행성계

    n = int(input())
    for _ in range(n):
        x, y, r = map(int, input().split())
        start = ((x1-x)**2 + (y1-y)**2)**0.5  # 출발지에서 행성 중심까지의 거리
        end = ((x2-x)**2 + (y2-y)**2)**0.5  # 도착지에서 행성 중심까지의 거리

        # 모두 안에 있으면 지나갈 필요 없음
        if start < r and end < r:
            pass
        # 시작점이나 도착점이 안에 있을 경우 +1
        elif start < r:
            res += 1
        elif end < r:
            res += 1
    print(res)

 만약 출발지와 도착지 모두 감싸고 있다면, 굳이 지나갈 필요가 없으므로 무시합니다.