[백준 1004] 어린 왕자

문제 보기

예전에 오답처리를 2번 받고나서 귀찮아서 안 푼 문제인 것 같다.

문제 해결을 위한 방법은 매우 간단하다.

어린 왕자가 출발점에서부터 도착점까지 최소한의 행성계의 이탈/진입 횟수를 측정하는 것인데, 이는 한 가지의 조건만 안다면 해결할 수 있다.

핵심 조건은 각 행성계를 기준으로, 출발점과 도착점 서로 행성계의 안팎으로 다른 위치에 있어야 한다는 것이다.

위의 그림에 해당하는 조건을 만족하는 행성계의 갯수를 세면 정답이다.

소스코드에서 위의 조건에 해당하는 조건문은 19번째 줄이다.

점과 점 사이의 거리를 측정하기 위해서 원래 sqrt를 써야하지만, 나는 sqrt를 쓰지 않는 대신 행성계의 반지름의 길이를 제곱해서 비교하였다.

import sys
 
t = int(sys.stdin.readline())
for _ in range(t):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    n = int(sys.stdin.readline())
    
    planet_list = list()
    result = set()
    for _ in range(n):
        planet_list.append(list(map(int, sys.stdin.readline().split())))
    
    count = 0
    for x, y, r in planet_list:
        d1 = (x1 - x)**2 + (y1 - y)**2
        d2 = (x2 - x)**2 + (y2 - y)**2
        rr = r**2
        
        if d1 < rr < d2 or d2 < rr < d1:
            count += 1
    print(count)