백준 1004번 어린 왕자 JAVA

링크텍스트

설명

각 행성계는 원(circle) 이고
어린 왕자가 이동하면서 원 안으로 들어가거나 / 밖으로 나올 때마다 1번 카운트된다.

따라서 출발점과 도착점이 서로 다른 포함 상태에 있는 행성계의 개수를 세면 된다.

어떤 행성계(원)에 대해:

출발점이 원 안에 있고 도착점이 밖에 있으면 → 1번 진입/이탈
출발점이 밖 도착점이 안이면 → 1번 진입/이탈
둘 다 안이거나 둘 다 밖이면 → 0번
출발점이 그 원 안에 있는지 XOR 도착점이 그 원 안에 있는지

(x - cx)² + (y - cy)² < r²
출발점과 도착점이 서로 다른 쪽에 있는 원의 개수를 세면 됨.
시간복잡도: O(T*N), 공간복잡도: O(1)

회독

• [ x ] 1회
• 2회
• 3회

코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        while(t-->0){
            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 answer = 0;
            for(int i=0;i<n;i++){
                st = new StringTokenizer(br.readLine());

                int cx = Integer.parseInt(st.nextToken());
                int cy = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken()); 

                boolean start = checkInside(x1, y1, cx, cy, r);
                boolean end = checkInside(x2, y2, cx, cy, r);

                if(start!=end) answer++;
            }

            sb.append(answer).append("\n");
        }

        System.out.print(sb);
    }

    public static boolean checkInside(int x, int y, int cx, int cy, int r){
        int dx = x-cx;
        int dy = y-cy;
        return (dx*dx)+(dy*dy) < r*r;
    }
}