백준 - 1004번(기하)

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

1004번: 어린 왕자

import sys

n = int(sys.stdin.readline())

for _ in range(n):
    tmp = [0,0,0,0]
    tmp = list(map(int,sys.stdin.readline().split()))
    s = [tmp[0],tmp[1]]
    e = [tmp[2],tmp[3]]

    m = int(sys.stdin.readline())
    cnt = 0
    for i in range(m):
        arr = list(map(int,sys.stdin.readline().split()))
        if ((s[0] - arr[0])**2) + ((s[1] - arr[1])**2) < arr[2] ** 2 and ((e[0] - arr[0]) ** 2) + ((e[1] - arr[1]) ** 2) > arr[2] ** 2:
            cnt = cnt + 1
        if ((e[0] - arr[0]) ** 2) + ((e[1] - arr[1]) ** 2) < arr[2] ** 2 and ((s[0] - arr[0])**2) + ((s[1] - arr[1])**2) > arr[2] ** 2:
            cnt = cnt + 1

    print(cnt)

일다 어린 왕자가 최소 횟수로 행성계를 최소한으로 통과해야 한다.
그럼 어떤 경우에 어린왕자가 행성계를 통과할 수밖에 없는지 생각해 봐야 한다.
어린 왕자가 원 안에 있거나 목적지가 원 안에 있을 때 반드시 지나갈 수밖에 없다.
다만 어린 왕자와 목적지가 같은 원 안에 있는 경우도 있으니깐 그걸 방지하기 위해서 어린 왕자는 원안에 있고 목적지는 다른 원 안에 있을 때만 cnt를 1씩 증가시켜준다. 그럼 최종적으로 나온 cnt가 답이다.

번외로 자신이 사랑하는 한송이 장미를 위해 살아가고 그걸 위해 먼 길을 떠나는 어린 왕자,, 넘 낭만적이고,,
solved.ac를 보니깐 기하학 문제를 거의 안 풀어서 재밌는 기하학 문제를 좀 풀어볼까 합니다.
백준 첨 시작할 때 위 문제와 비슷한 문제로 터렛을 재밌게 풀었던 기억이 있습니다.
BFS도 빨리 재밌어지면 좋겠네요..