백준 1004번
https://www.acmicpc.net/problem/1004

문제

후기

⏰ 풀이시간 1.5시간 ++⏰

항상 익숙한 문제만 푸는 것 같아, 기하학 문제를 처음으로 도전해보았다.

한 30분 이상을 어떤 방식으로 문제에 접근해야할지 고민했다.

원의 위치를 받아서 점이 해당 원에 닿을 때 마다 + 해줘야 하나..?

동선은 어떻게 최적화 해야하지..? 기하학 문제가 사실은 BFS를 써야되는 문젠가..?

라는 얼토당토 않는 고민을 하다가, 그림판에 그림을 그려보다 보니 문제를 위한 해법을 얻게 되었다.

만약 출발점과 도착점이 둘다 같은 원 안에 있으면, 어떻게든 행성에 진입하지 않을 수 있는
루트는 존재한다.

또한 둘다 원 안에 들어있지 않아도, 행성에 진입하지 않을 수 있다.
출발점과 도착점 중 한 점만 원에 들어있다면 행성에 진입하게 된다.

위의 그림을 보면, 한 행성 안에 들어가있는 도착점과 출발점은 행성의 출입이 필요하지 않고,

어떠한 원에도 들어가있지 않은 도착점과 출발점도 마찬가지로 행성의 출입이 필요하지 않다.

도착점 혹은 출발점 중 하나의 점만이 원에 들어가 있을 때 행성의 출입이 발생한다.

x1,x2,y1,y2로 출발점, 도착점의 좌표를 받고,

두 점사이의 거리를 계산하는 수학적 공식으로 start와 end 점을 저장한다.

도착점 혹은 출발점 중 하나의 점이 원에 들어가 있을 때 cnt+=1 을 하고 정답을 출력한다.

나의 풀이

import sys
input=sys.stdin.readline

for _ in range(int(input())):

    cnt = 0
    x1, y1, x2, y2= map(int,input().split()) # 출발점 x1y1 도착점 x2y2

    for _ in range(int(input())): #행성의 개수 

        a, b, r = map(int,input().split())  

        # 출발점 도착점이 둘다 똑같은 원 안에 있으면 pass
        # 출발점 도착점 둘다 원 안에 들어있지 않으면 pass
        # 출발점 도착점 중 한 점만 원에 들어있다면 cnt +=1

        start = ((abs( x1 - a)) **2 + (abs( y1 - b)) ** 2 ) ** 0.5  #행성중심 ~ 시작점 
        end =   ((abs( x2 - a)) **2 + (abs( y2 - b)) ** 2)  ** 0.5  #행성중심 ~ 도착점

        if   ( r > start and end > r ):
            cnt +=1
        elif ( start > r and end < r):
            cnt +=1
        else:
            pass
    print(cnt)