[백준 1004] 어린 왕자 (python)

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

1004번: 어린 왕자

어린 왕자 문제

목표 지점까지 도착하기 위해서 최소 몇개의 원을 거쳐야 하는지 세보는 문제

특별한 코딩적 기술보단 수학적 접근으로 푸는 문제

내가 푼 정답코드

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())
    cnt = 0
    for _ in range(n):
        Cx, Cy, r = map(int, sys.stdin.readline().split())
        distance_start = ((Cx-x1)**2+(Cy-y1)**2)**(1/2) # 시작 지점부터 원까지 거리
        distance_end = ((Cx-x2)**2+(Cy-y2)**2)**(1/2) # 끝 지점부터 원까지 거리
        # 수학적 조건
        if (distance_start < r and distance_end > r) or (distance_start > r and distance_end < r):
            cnt += 1
    print(cnt)

아이디어는 간단하다

시작 지점부터 원까지 거리가 반지름보다 작고 끝지점부터 원까지의 거리가 반지름보다 크거나

원까지 거리가 반지름보다 크고 끝지점부터 거리가 반지름보다 작으면 된다

 

---

느낀 점

터렛 문제에 이어 100% 수학적으로 구현하는 문제이다. 수학적 접근으로 특별한 알고리즘 기술 없이 구현하니 쉽게 해결 할 수 있던 문제였다.