백준 1004번 어린 왕자 [JAVA]

문제 출처: https://www.acmicpc.net/problem/1004

1004번: 어린 왕자

 

 

Sol)

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        int tc, numberOfGalaxy;
        int[] xys = new int[4], galaxy = new int[3];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        tc = Integer.parseInt(br.readLine());

        while(tc > 0){

            int cnt = 0;

            String[] xyxy = br.readLine().split(" ");
            for(int i = 0; i < xys.length; i++)
                xys[i] = Integer.parseInt(xyxy[i]);

            numberOfGalaxy = Integer.parseInt(br.readLine());

            while(numberOfGalaxy > 0){

                String[] xyr = br.readLine().split(" ");
                for(int i = 0; i < galaxy.length; i++)
                    galaxy[i] = Integer.parseInt(xyr[i]);

                double startCircleVal = Math.pow(xys[0] - galaxy[0], 2) + Math.pow(xys[1] - galaxy[1], 2);
                double destinationCircleVal = Math.pow(xys[2] - galaxy[0], 2) + Math.pow(xys[3] - galaxy[1], 2);
                double squaredRadius = Math.pow(galaxy[2], 2);

                if(startCircleVal <= squaredRadius && destinationCircleVal <= squaredRadius){
                    numberOfGalaxy--;
                    continue;
                }
                else if(startCircleVal <= squaredRadius || destinationCircleVal <= squaredRadius)
                    cnt++;

                numberOfGalaxy--;
            }
            System.out.println(cnt);
            tc--;
        }
        br.close();
    }
}

 

• 풀이 방향

그림은 복잡해보이나 풀이 방향은 간단할 것 같다. 맞닿거나 교차하는 행성계 경계가 없다고 했으므로, 출발점과 도착점이 행성계 경계 안에 있지 않는 이상 반드시 해당 행성계는 지나지 않을 수 있다. 따라서 출발점을 포함하고 있는 원(행성 경계)의 개수와 도착점을 포함하고 있는 원(행성 경계)의 개수를 더해주면 답이 나오겠다. 

 

• 풀이

x1, y1, x2, y2, 행성계 원의 중심좌표 + 반지름 좌표등 받아야 하는 변수들이 많으므로 각각 배열로 선언해 주었다. 그 후, StringTokenizer를 이용해서 각 값들을 받아도 되지만,

StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead. (https://docs.oracle.com/javase/8/docs/api/java/util/StringTokenizer.html)

위와 같이 오라클 공식 문서에서 StringTokenizer의 사용을 장려하고 있지 않기때문에 String 클래스의 split메소드를 사용했다.

그 후는 각 행성계의 원의 방정식에 출발점과 도착점을 대입해 보고, 해당 값이 반지름의 제곱보다 작거나 같다면 원 안에 있다는 말이므로 count를 올려준다. 단, 출발점과 도착점이 같은 원 안에 있을 경우에는 해당 원을 통과하지 않아도 되므로 count하지 않는다.

 

• 문제에 대한 사견

그림만 괴랄한 문제였던 것 같다.