1004. 어린왕자 (자바, Java)

 

처음에 뭔가 복잡해보여서 쫄았는데, 생각보다 간단하다.

어린왕자의 출발점에서 도착점까지 점과 점 사이로 연결되는데, 행성(원)의 진입과 이탈을 최소화한다

= 반드시 통과할때 지나가야 하는 것만 지나야 한다. 라는것이다. 그럴러면 원이 출발점과 도착점 사이에 있으면 된다.

즉, 출발점이 원의 외부에 있고, 도착점이 원의 내부에 있거나, 그 반대 (출발점이 원의 내부, 도착점이 원의 내부)에 있어야 한다는 것이다.

 

원의 외부인지 내부인지는, 원의 중심으로부터 점까지의 거리 d와 반지름 r을 비교하면 된다. d<r이면 내부, d>r이면 외부이다. d=r이면 원 위에 있는 셈인데, 문제에서 친절하게 행성의 경계에 있는 경우는 입력값에 없다고 알려주고 있다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t=Integer.parseInt(br.readLine()); // 테스트케이스의 수 T
				
		StringBuilder sb = new StringBuilder();
				
		for (int i=0; i<t; i++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			//출발점과 도착점을 받을 StringTokenizer
			int[] start = new int[2];
			int[] end = new int[2];
			
			start[0] = Integer.parseInt(st.nextToken());
			start[1] = Integer.parseInt(st.nextToken());
			end[0] = Integer.parseInt(st.nextToken());
			end[1] = Integer.parseInt(st.nextToken());
			
			int n = Integer.parseInt(br.readLine());
			//행성계의 수 N
			int c[][] = new int[n][3];
			//각 행성계의 중점과 반지름을 받을 배열
			
			int count=0; // 행성의 진입과 이탈을 셀 카운트값으로 최종출력값.
			
			for (int j=0; j<n; j++) {
				StringTokenizer st2 = new StringTokenizer(br.readLine()," ");
				c[j][0] = Integer.parseInt(st2.nextToken());
				//행성계의 x좌표
				c[j][1] = Integer.parseInt(st2.nextToken());
				//행성계의 y좌표
				c[j][2] = Integer.parseInt(st2.nextToken());
				//행성계의 반지름 r
				
				if (distance(start[0], start[1], c[j][0], c[j][1])<c[j][2]
						&& distance(end[0], end[1], c[j][0], c[j][1])>c[j][2]) {
					count++;
				} else if (distance(start[0], start[1], c[j][0], c[j][1])>c[j][2]
						&& distance(end[0], end[1], c[j][0], c[j][1])<c[j][2]) {
					count++;
				} // 행성계를 진입/이탈하려면, 시작점과 도착점 중 하나는 밖에, 나머지 하나는 안에 위치해야한다.				
			}			
			
			sb.append(count + "\n");
			
		}
		
		System.out.println(sb);
		
	}
	
	public static double distance(int x1, int y1, int x2, int y2) {
		return Math.sqrt(Math.pow(x1-x2,2)+Math.pow(y1-y2, 2));
	} // 거리를 구할 매소드 생성

}