어린왕자

in Algorithm on 백준


백준 [1004] 어린왕자

문제보기
Alt text

풀이

모든 행성을 돌며 출발점과 도착점이 포함되는지 파악한다.

  1. 두 점이 모두 행성계에 포함되지 않는 경우 : 진입할 필요 없음
  2. 두 점이 모두 행성계에 포함되는 경우 : 진입할 필요 없음
  3. 두 점 중 한 점만 행성계에 포함되는 경우 : 진입 필요

소스코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        for (int tc = 0; tc < T; tc++) {
            // 출발점
            int departureX = sc.nextInt();
            int departureY = sc.nextInt();

            // 도착점
            int arrivalX = sc.nextInt();
            int arrivalY = sc.nextInt();

            int n = sc.nextInt();
            int[][] planets = new int[n][3]; // 행성계
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < planets[i].length; j++) {
                    planets[i][j] = sc.nextInt();
                }
            }

            countPlanetsBoundary(departureX, departureY, arrivalX, arrivalY, planets);
        }
    }

    private static void countPlanetsBoundary(int departureX, int departureY, int arrivalX, int arrivalY, int[][] planets) {
        int n = planets.length;
        int planetBoundaryCnt = 0;

        for (int p = 0; p < n; p++) {
            int planetX = planets[p][0];
            int planetY = planets[p][1];
            int planetR = planets[p][2];

            double departureDistance = Math.sqrt(((departureX - planetX) * (departureX - planetX)) + ((departureY - planetY) * (departureY - planetY)));
            double arrivalDistance = Math.sqrt(((arrivalX - planetX) * (arrivalX - planetX)) + ((arrivalY - planetY) * (arrivalY - planetY)));

            // 출발점, 도착점 모두 현재 행성계에 포함되는 경우 -> 진입 할 필요 없음
            if (departureDistance <= planetR && arrivalDistance <= planetR) {
                continue;
            }
            if (departureDistance <= planetR || arrivalDistance <= planetR) {
                planetBoundaryCnt++;
            }
        }

        System.out.println(planetBoundaryCnt);
    }
}