[파이썬/백준1004/힌트] 어린왕자

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

1004번: 어린 왕자

실버3, 문제의 의도만 파악하면 쉬운 문제다.

기하학 문제들은 누누히 말하지만, 일단 문제가 의도하는바를 명확히 파악하기만 하면, 코드는 어렵지 않게 짤 수 있다는 공통점이 있다.

이 문제도 마찬가지, 의도를 파악하지 못했다면 이걸 어떻게 구현해야될지 막막할테지만 의도만 파악한다면 아주 쉽게 풀 수 있을 것이다.

힌트부터 하나씩 확인하면서 스스로 풀어가보자.

원의 갯수는 아무짝에 쓸모없다. 30만 광년을 돌아서 가더라도 행성계 진입, 이탈횟수만 최소화 하면 된다. 

즉, 출발점에서 도착점을 선으로 이었을 때 한번은 반드시 지나야만 하는 원의 갯수를 구하면 된다.

 

위 힌트는 큰 도움이 되지 않았는가? 

출발지점이나 도착지점이 어떤 원 내부에 있다면, 그 원은 반드시 한 번은 지나야만 한다.

(단, 출발지점과 도착지점을 둘 다 포함하는 하나의 원은 제외한다.)

 

결정적인 힌트 이것까지 봤다면 이제는 정말 풀어보자

원의 중점과 출발지점(또는 도착지점) 사이의 거리, 그 원의 반지름의 길이의 관계를 생각해보면 출발지점이나 도착지점이 주어진 원의 내부에 있는지 판단할 수 있다.

 

정답코드는 아래와 같이 작성했다.

T = int(input())

lst = []
for i in range(T):
    x1, y1, x2, y2 = map(int,input().split())
    N = int(input())
    s = 0
    for i in range(N):
        x_c, y_c, r_c = map(int,(input().split()))
        Start_distance = ((x_c - x1)**2 + (y_c - y1)**2) ** 0.5
        End_distance = ((x_c - x2)**2 + (y_c - y2)**2) ** 0.5
        if Start_distance < r_c: # 출발지점이 원 내부에 속하면
            s+=1 # Count ++
        if End_distance < r_c: # 도착지점이 원 내부에 속하면
            s+=1 # Count ++
        if Start_distance < r_c and End_distance <r_c: # 출발점과 도착점이 하나의 원 내부에 둘 다 속하면
            s-=2 # Count - 2
    lst.append(s)

for i in lst:
    print(i)