[백준 1004] 어린 왕자

[BanApp]

https://www.acmicpc.net/problem/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도 빨리 재밌어지면 좋겠네요..
근데 코테에 기하학 문제는 잘 안나오나요? 근데 나였어도 안낼듯,,

[ghdcksgml1]

ㅋㅋㅋㅋㅋ 코테에서는 기하학 증명이 어려워서 잘 안냅니다. 대회에서는 엄청 많이나와요.

내 기하학 지식은 어디로 갔을까...

[BanApp]

역시 재밌는건 시험에 안나오는군요.