[BAEJOON] 1004 어린 왕자

어린왕자 문제

문제 요약

• 알고리즘 분류: 기하학
• 문제 난이도: Silver3
• 문제 내용:
  • 각 테스트케이스에서  출발점 (x1, y1) → 도착점 (x2, y2) 행성계 진입/이탈 횟수를 출력한다.
• 사이트 주소: https://www.acmicpc.net/problem/1004

1004번: 어린 왕자

문제 풀이

1. 출발점과 도착점 행성 중심점 거리를 구한다.
2. 각 거리와 행성의 반지름 길이보다 작을 경우에는 행성안에 있다.
3. 출발점과 도착점에서 행성 중심점 거리가 행성의 반지름 갈이가 둘 다 작을 경우에는 행성 안에 이동하므로 제외 한다.
4. 그 외 행성의 반지름 길이가 둘 중 하나 작을 경우 count를 증가 한다.

PYTHON

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    x1, y1, x2, y2 = map(int, input().split())
    cnt = 0
    for _ in range(int(input())):
        x, y, r = map(int, input().split())
        r *= r
        d1 = (x1 - x) ** 2 + (y1 - y) ** 2
        d2 = (x2 - x) ** 2 + (y2 - y) ** 2
        if d1 < r and d2 < r:
            continue
        elif d1 < r or d2 < r: cnt += 1
    print(cnt)

JAVA

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int T = Integer.parseInt(br.readLine());
	    StringTokenizer st;
		
		for(int t = 0; t < T; t++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			int n = Integer.parseInt(br.readLine());
			int count = 0;
			for(int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				int r = Integer.parseInt(st.nextToken());
				r = r * r;
				int d1 = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
				int d2 = (x2 - x) * (x2 - x) + (y2 - y) * (y2 - y);
				
				if(d1 < r && d2 < r) {
					continue;
				}else if(d1 < r || d2 < r) {
					count++;
				}
			}
			System.out.println(count);
		}
	    
	}
	    
}