1004번: 어린 왕자

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중점과 반지름 (cx, cy, r)이 주어진다. 입력제한은 다음과 같다. (-1000 ≤ x1, y1, x2, y2, cx, cy ≤ 1000, 1 ≤ r ≤ 1000, 1 ≤ n ≤ 50) 좌표와 반지름

www.acmicpc.net

근무 하면서 푼 문제이다.

고민하다가 후임이 좋은 풀이법을 알려주었다.

 

출발점과 도착점이 주워지고, 행성의 개수가 7개라 하면 아래 표 처럼 만들 수 있다. 원은 (x-x1)**2 + (y-y1)**2 = r**2 방정식을 따르는데, 출발점을 각각의 행성에 대입해서 r**2 보다 작으면 출발점이 행성 안에 있다라는 뜻이 된다. 이때의 값은 O 라고 하고 아닐시 X라고 표시한다. 

  1번 행성 2번 행성 3번 행성 4번 행성 5번 행성 6번 행성 7번 행성
출발점 O O X X X X X
도착점 O X O X X X X

 

위 표를 분석해보면 다음과 같다.

1번 행성은 각각 O, O 결과이다. 이 뜻은 출발점과 도착점이 1번 행성 안에 존재 한다는 뜻이다. 즉 이러한 경우는 제외하면 된다. 2번째 행성은 O,X 결과이다. 이 뜻은 출발점은 2번 행성 안에 있지만, 도착점은 밖에 있다는 뜻이다. 즉, 출발점과 도착점을 잇는다면, 무조건 한 점으로 만나게 된다. 

 

그럼 위 표의 결과를 각각 XOR 연산을 하면 최종적인 결과를 얻어 낼 수 있을 것이다. 위 표의 결과는 2 이다.

 

아래는 python3 으로 코드를 구현한 것이다.

 

# -*- coding: utf-8 -*-
def isInCircle(point, circle):
    answer = list()
    
    for c in circle.values():
        result = eval(c[0].format(point[0], point[1]))
        
        if result < c[1]:
            answer.append(1)
        else:
            answer.append(0)
    return answer


if __name__ == "__main__":
    r = list()
    # 테스트 케이스의 개수 T
    testCase_count = int(input(""))
    
    for count in range(0, testCase_count):
        #각각의 테스트 케이스에 대한 출발점과 도착점 입력
        start_end = list(map(int, input("").split(" ")))
        
        # 출발점과 도착점을 분리하여 저장
        startPoint = [start_end[0],start_end[1]]
        endPoint = [start_end[2],start_end[3]]
        
        # 행성의 개수 n
        n = int(input(""))
        circle = dict()
        for i in range(0,n):
            input_data = list(map(int ,input("").split(" ")))
            circle[i] = ["({} - ("+str(input_data[0])+")) ** 2 + ({} - ("+str(input_data[1])+")) ** 2", int(input_data[2]) ** 2]
        
        result1 = isInCircle(startPoint, circle)
        result2 = isInCircle(endPoint, circle)
        
        count = 0
        for i in range(0, n):
            if result1[i] ^ result2[i] == 1:
                count += 1
        
        r.append(count)
        
    for i in range(0,len(r)):
        print(r[i])

 

'BaekJoon' 카테고리의 다른 글

[BaekJoon] - 10936 base64 디코딩  (0) 2019.10.12
[BaekJoon] - 10935 base64 인코딩  (0) 2019.10.12
[BaekJoon] - 10845 큐  (0) 2019.10.12
[BaekJoon] - 10828 스택  (0) 2019.10.12
[BaekJoon] 1158번 조세퍼스 문제  (0) 2019.10.10
[BaekJoon] - 1004번 어린왕자  (0) 2019.10.05