[python] 1004. 어린 왕자

문제 출처

1004. 어린 왕자

 

풀이

A 포인트부터 B 포인트까지 이동할때 거쳐야 할 최소의 행성계 진입/이탈 횟수를 구한다.

행성계의 좌표와 반지름이 주어지므로 A, B포인트와 행성계 와의 거리를 통해 행성계 궤도에 진입 여부를 확인한다. 이때 최소의 횟수를 구하는 것 이므로 진입/이탈 둘 다 하는 경우는 없다고 볼 수 있다.

따라서 최소의 행성계 진입을 통해 이동가능한 경우는 다음과 같다.

• 한 개 이상의 행성계 내부에 A, B 포인트 모두 존재
• 한 개의 행성계 내부에는 A, B 포인트 중 하나만 존재
• A, B 포인트 모두 행성계 외부에 존재

위 경우를 고려해서 코드를 짜면 다음과 같다.

# 특정 포인트가 행성계 내부에 존재 유무 확인
def inCircle(planet, x, y):
    c1, c2, r = planet
    d = ((c1-x)**2 + (c2-y)**2)**0.5    # 행성 좌표와 포인트와의 거리
    if d < r:
        return True
    return False


T = int(input())        # 테스트케이스 갯수 입력
for _ in range(T):        
    x1, y1, x2, y2 = map(int, input().split())
    N = int(input())    # 행성계 갯수 입력
    planets = []        # 입력받을 행성계를 저장할 빈 리스트
    for __ in range(N):
        planets.append(tuple(map(int, input().split())))

    cnt = 0
    for planet in planets:
        # 두 포인트 모두 한 행성계 내부에 존재
        if inCircle(planet, x1, y1) and inCircle(planet, x2, y2):
            continue
        # 한 행성계 내부에는 한 포인트만 존재
        elif inCircle(planet, x1, y1) or inCircle(planet, x2, y2):
            cnt += 1
        # 두 포인트 모두 행성계 밖에만 존재
        else:
            continue

    print(cnt)