[BOJ] 1004. 어린왕자 - JAVA

🔗 문제

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

1004번: 어린 왕자

 

🧩 풀이 및 코드

문제 유형 : 수학, 기하학

 

그림에 겁먹을 것 없이 풀이과정은 은근 단순했다.

진입/이탈의 최소 횟수를 구하는 것이기 때문에 출발점과 도착점이 원 밖에 있다면, 진입/이탈 없이 돌아서 가면 된다.

출발점과 도착점이 둘 다 원 내부에 있다면 진입/이탈이 없기 때문에 횟수로 치지 않는다.

즉, 출발점 또는 도착점 중 하나가 원 내부에 있다면 무조건 진입/이탈을 해야 하므로 이 경우의 갯수만 세면 된다.

이 경우는 원의 중심과 출발점, 도착점 각각의 거리를 구했을 때 원의 반지름보다 작다면 각 점이 원 내부에 있다는 뜻이다. 

두 점이 모두 원 내부에 있거나 밖에 있어 진입/이탈이 없는 경우

출발점 또는 도착점이 원 내부에 있어 이탈이 발생하는 경우

 

두 점 사이의 거리를 구하는 공식은 다음과 같다. 

전체 코드

import java.io.*;
import java.util.*;

public class Main_bj_1004_어린왕자 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_1004.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		int start_x=0, start_y=0, end_x=0, end_y=0, N=0, cnt=0, x=0, y=0, r=0;
		
		StringBuilder sb = new StringBuilder();
		while(T-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			start_x = Integer.parseInt(st.nextToken());
			start_y = Integer.parseInt(st.nextToken());
			end_x = Integer.parseInt(st.nextToken());
			end_y = Integer.parseInt(st.nextToken());
			
			N = Integer.parseInt(br.readLine());
			cnt = 0;
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				x = Integer.parseInt(st.nextToken());
				y = Integer.parseInt(st.nextToken());
				r= Integer.parseInt(st.nextToken());
				
				double d1 = Math.sqrt((x-start_x) * (x-start_x) + (y-start_y) * (y-start_y));
				double d2 = Math.sqrt((x-end_x) * (x-end_x) + (y-end_y) * (y-end_y));
				
				if((d1 < r && d2 < r) || (d1 > r && d2 > r)) continue;
				cnt++;
			}
			
			sb.append(cnt).append("\n");
		}
		
		System.out.println(sb.toString());
		br.close();
	}

}

 

---

Reference

https://blog.itcode.dev/posts/2021/05/22/a1004

[백준 / JAVA] 백준 알고리즘 1004번 어린 왕자 - 𝝅번째 알파카의 개발 낙서장

https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-1004-%EC%9E%90%EB%B0%94-%EC%96%B4%EB%A6%B0-%EC%99%95%EC%9E%90-BOJ-1004-JAVA

백준 1004 자바 - 어린 왕자 (BOJ 1004 JAVA)