[백준 1004 파이썬] 어린 왕자 (실버 3, 기하)

알고리즘 유형 : 기하
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    x1, y1, x2, y2 = map(int, input().split())
    n = int(input())
    count = 0
    for _ in range(n):
        c_x, c_y, r = map(int, input().split())
        # d1은 출발지에서 주어진 원의 중심까지의 거리
        # d2는 도착지에서 주어진 원의 중심까지의 거리
        d1 = ((c_x - x1)**2 + (c_y - y1)**2)**0.5
        d2 = ((c_x - x2)**2 + (c_y - y2)**2)**0.5
        
        # d가 r보다 작으면 원 안에 있단 뜻이고, 
        # 크면 원 밖에 있다는 뜻임
        # 하나는 원 안에 있고 하나는 원 밖에 있을 때
        # 이 원의 경계, 즉 행성계를 반드시 지나가므로
        # 카운팅해줌
        if (d1-r)*(d2-r) < 0:
            count += 1

    print(count)

풀이 요약

1. 주어진 원에 대해, 출발지가 원 안에 있고 도착지가 원 밖에 있거나, 출발지가 원 밖에 있고 도착지가 원 안에 있는 두 경우에 대해, 출발지에서 도착지로 이동하려면 반드시 이 원의 경계를 지나가야 한다.

   출발지, 도착지 둘 다 원 안에 있거나 원 밖에 있다면 이 원의 경계를 지나지 않고도 출발지에서 목적지로 도달할 수 있다.

2. 따라서 주어지는 원의 정보 각각에 대하여, 그 원의 중심과 출발지, 도착지까지의 거리 d1, d2를 구하고, 이 것과 반지름의 대소 관계로 출발지&도착지가 원 내부에 있는지 외부에 있는지를 알아내고,

   위의 원리를 적용하여 조건문으로 카운팅을 해준다.

배운 점, 어려웠던 점

• 기하 문제는 수학적으로 사고해야 풀이가 보임을 느꼈다. 많이 풀어봐야 익숙해질 것 같다.