[알고리즘] 백준 1004 : 어린 왕자 - JAVA

문제

1004번: 어린 왕자

문제이해

출발지의 좌표와 도착지의 좌표가 주어지며 n개의 행성의 좌표와 원의 반지름이 주어진다.

출발지에서 도착지까지 이동할 때 행성에 진입하고 이탈하게 되는데 최소한의 진입과 이탈을 하게 되는 경우의 수를 구해야 한다.

 

입력

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

• T
• x1 y1 x2 y2
• n
• cx cy r

출력

각 테스트 케이스에 대해 어린 왕자가 거쳐야 할 최소의 행성계 진입/이탈 횟수를 출력한다.

---

풀이

 

행성들이 출발 지점과 도착 지점을 포함하지 않는다면 이동할 때 진입과 이탈을 하지  않을 수 있습니다.

즉, 행성이 출발 지점 또는 도착 지점을 포함해야만 탈출과 진입이 있을 수 있습니다.

 

여기에서 주의할 점은 출발지점과 도착지점이 같은 행성에 존재한다면 내부에서의 이동이기에 탈출과 진입이 없다는 것입니다.

따라서 풀이를 하기 위해선 행성에 출발지점 또는 도착지점이 포함되는지 확인해야되는데 점과 점 사이의 거리를 구하고 반지름과 비교하면 원의 내부에 포함되는지 알 수 있습니다.

 

행성의 원점과 출발지점 또는 도착지점의 거리가 반지름의 길이보다 작다면 원에 포함되는 것이고 이를 카운트하면 되겠습니다.

---

코드

import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        
        for(int i = 0; i < T; i++){
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            
            int n = sc.nextInt();
            
            int answer = 0;
            for(int j = 0; j < n; j++){
                int x = sc.nextInt();
                int y = sc.nextInt();
                int r = sc.nextInt();
                
                //	출발지점, 도착지점과 행성원점과의 거리
                double start = Math.sqrt(Math.pow(x1-x, 2) + Math.pow(y1-y, 2));
                double end = Math.sqrt(Math.pow(x2-x, 2) + Math.pow(y2-y,2));
                if((start < r || end < r)&&!(start < r && end < r))answer++;
            }
            
            System.out.println(answer);
        }
    }
}