백준 1004 어린왕자

import sys
 
# 시작점 혹은 도착점이 원 안에 들어있는지 확인
def in_circle(x,y,r,temp_x,temp_y):
    if r**2 > (( x - temp_x)**2) + ((y - temp_y)**2):
        return True
    else: return False
 
# 테스트 케이스
T = int(sys.stdin.readline())
 
result_print = []
#테스트 케이스 동안
for i in range(T):
    #시작점, 도착점
    start_x, start_y, end_x, end_y = map(int, sys.stdin.readline().split())
    # 행성 개수 받기
    planet = int(sys.stdin.readline())
    # 행성 개수만큼 행성 좌표 받기
    result = 0
    for j in range(planet):
        planet_x, planet_y, r = map(int,sys.stdin.readline().split())
        # 출발점과 도착점이 원 안에 있을 경우만 생각
        if in_circle(planet_x,planet_y,r,start_x,start_y) and in_circle(planet_x,planet_y,r,end_x,end_y):
            pass
        elif in_circle(planet_x,planet_y,r,start_x,start_y):
            result += 1
        elif in_circle(planet_x,planet_y,r,end_x,end_y):
            result += 1
    result_print.append(result)
 
for k in result_print:
    print(k) 

적혀있는 문제와 좌표와 원이 난무하는 그림을 보면 정말 풀기 싫어지는 문제 하지만 어떻게 풀지 초반에 생각만 잘 하면 쉽다

처음에는 테스트 케이스를 받고 해당 테스트 케이스 수만큼 행성의 좌표를 받아서 저장 받는건 쉽게 할 수 있고 문제는 어떻게 행성으로 진입/이탈하는 것을 아느냐이다.

보면 어떤 행성이 어디에 있건 간에 어린왕자가 출발하고 도착점에 도달하면서 진입/이탈하는 경우는 출발점이나 도착점이 원 안에 있을 경우밖에 없다. 다른 행성들은 어린왕자가 알아서 무빙치면서 피해갈 것이기 때문에 해당 경우만 생각하면 된다. 이미 원 안에 있으면 무조건 진입/이탈이 필요하니까.

하지만 이 경우에도 생각해야 할 것이 출발점과 도착점이 모두 같은 원 안에 있을 경우를 생각해야 한다. 출발점과 도착점이 같은 원 안에 있다면 굳이 진입/이탈할 필요가 없이 행성 안에서 이동할 수 있기 때문이다.

그러면 우리가 생각할 수 있는 로직은

• 출발점과 도착점이 같은 원 안에 있을 경우는 패스
• 출발점만 원 안에 있을 경우에 진입/이탈 횟수 1회 추가
• 도착점만 원 안에 있을 경우에 진입/이탈 횟수 1회 추가 이다. 이 경우만 생각해주면 나머지는 어린왕자가 알아서 할 것이다.

원 안에 있는지 확인하는 방법은 쉽다. 피타고라스의 방정식을 이용하면 된다. x^2 + y^2 = r^2 이므로 해당 반지름의 제곱보다 출발점/도착점의 좌표가 작으면 안에 있다고 생각할 수 있다.

def in_circle(x,y,r,temp_x,temp_y):
    if r**2 > (( x - temp_x)**2) + ((y - temp_y)**2):
        return True
    else: return False

해당 함수는 행성의 x,y좌표와 반지름, 출발점/도착점을 받아 만약 행성 안에 있으면 True를 반환한다. 이럴 경우에만 result에 1을 추가해주면 된다.

하지만 메모리는 오지게 갉아먹는 모오습