[Java] 백준 풀기 1004 - 어린 왕자

자바 백준 1004번

실버 3

https://www.acmicpc.net/problem/1004

1004번: 어린 왕자

 

 

 

 

 

문제 보기

분류: 수학, 기하학

 

 

 

 

 

문제 풀기

문제에서 요구하는 횟수를 구하기 위해서 출발점 또는 도착점이 주어지는 원들의 안에 위치하는지 판단한다. 점이 원안에 있어야 경계면을 지나기 때문이다. 이때, 출발점과 도착점이 동시에 원안에 위치할 때에는 이 판단이 성립하지 않으므로 이는 제외한다.

 

 

한 점과 원의 정보가 주어졌을때 점이 안에 있는지 판단하기 위해서는 점과 원의 중심사이의 거리를 계산하여 이 거리가 원의 반지름보다 작아야함을 이용한다.

    // 점이 원 안에 있는지 확인하는 메서드
    boolean containsPoint(Point p) {
        double distance = Math.sqrt(Math.pow(p.x - center.x, 2) + Math.pow(p.y - center.y, 2));
        return distance <= radius;
    }

 

 

출발점과 도착점이 주어진 원안에 있는지 판단한 후, 둘 중 하나의 점만 원 안에 있을때 카운트한다.

            // 하나의 점만 원안에 존재할 때 카운트
            if (p1Inside && !p2Inside) {
                count++;
            } else if (!p1Inside && p2Inside) {
                count++;
            }

 

 

 

 

 

코드 보기

import java.util.Scanner;
 
class Point {
    int x;
    int y;
    
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
class Circle {
    Point center;
    int radius;
    
    Circle(int cx, int cy, int r) {
        this.center = new Point(cx, cy);
        this.radius = r;
    }
    
    // 점이 원 안에 있는지 확인하는 메서드
    boolean containsPoint(Point p) {
        double distance = Math.sqrt(Math.pow(p.x - center.x, 2) + Math.pow(p.y - center.y, 2));
        return distance <= radius;
    }
}
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 테스트 케이스의 개수
        int T = sc.nextInt();
        
        for (int t = 0; t < T; t++) {
            // 점 좌표 입력 받기
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            
            // 원의 개수 입력 받기
            int n = sc.nextInt();
            
            // 원 정보를 저장하는 배열
            Circle[] circles = new Circle[n];
            
            for (int i = 0; i < n; i++) {
                // 원의 중점과 반지름 입력 받기
                int cx = sc.nextInt();
                int cy = sc.nextInt();
                int r = sc.nextInt();
                circles[i] = new Circle(cx, cy, r);
            }
            
            // 원안에 출발점 또는 도착첨이 있는지 판별하여 카운트하는 메서드
            int result = countPointsInCircles(new Point(x1, y1), new Point(x2, y2), circles);
            
            System.out.println(result);
        }
    }
    
    // 원 안에 점이 위치하는 개수 계산 메서드
    private static int countPointsInCircles(Point p1, Point p2, Circle[] circles) {
        int count = 0;
        
        for (Circle circle : circles) {
            // 출발점 또는 도착점이 주어진 원안에 있는지 판단
            boolean p1Inside = circle.containsPoint(p1);
            boolean p2Inside = circle.containsPoint(p2);
            
            // 하나의 점만 원안에 존재할 때 카운트
            if (p1Inside && !p2Inside) {
                count++;
            } else if (!p1Inside && p2Inside) {
                count++;
            }
        }
        
        return count;
    }
    
}