[java] 정올 - 사람 감시

문제

정올 - 사람 감시
2개의 레이더로 감시를 할 수 없는 최소 인원의 수를 구하는 문제

• 제한 사항
  감시해야하는 사람 수 N : 1 <= N <= 5,000
  감시망의 넓이 K : 0 <= K
  원주율을 사용할 경우, 원주율 값은 3.141

• 예시
  
  그림과 같은 상황이 감시하지 못하는 최소인원이 2인 경우이다

풀이

모든 부연설명에는 이유가 있다는 법을 알게해준 문제,,
문제에서 힌트로 준게 있었다 (나중에 이해했지만)

문제를 풀기 위해 원주율을 사용할 경우 원주율 값은 3.141 이라고 가정한다.

그건 바로 이 부분인데,
원주율 값 : 3.141, 문제에서 준 예시에도 총 넓이의 합인 K또한 40.833으로
둘다 소수점 세번째자리까지 나와있다
그래서 문제를 풀 때도 이 점을 이용해야한다

두 레이더망의 크기 K

두 개의 레이더망의 크기는 합쳐서 K가 되야한다
K보다 작아도 되지만 최대한 많은 사람을 감시해서 최소인원이 영역 외에 존재해야하므로
K와 같다고 생각을 해보자

즉, 각각의 반지름의 제곱의 합을 K라고 생각하고 조금씩 값을 바꿔가며 확인을 할 것이다
이때 값을 어떤 단위로 나누느냐, 아까 위에서 말했던 소수 세번째자리를 이용해서
1000으로 나눈 값을 더하고 빼가며 확인한다

나눈값을 더하고 뺀다의 의미는,
K = 200이고 소수점 아래 2번째까지 원주율(3.14)이 주어진 경우라면,
1 : 99 비율로 쪼개서 증감시키면서 두 레이더망의 크기를 조절한다는 얘기

사람위치로부터 레이더망까지의 거리

입력받을때 두 레이더까지의 거리를 각각 계산해서 배열에 저장했다

이 때 피타고라스의 정의를 이용했다
근데 루트는 씌우지 않을거다.. 왜냐면
레이더의 범위 안에 있는지(레이더의 반지름보다 작은지) 확인할 때
이미 제곱된 반지름(r^2)을 사용할 것이기 때문이다

준비는 끝났고, 두개의 레이더망의 반지름에 따라
사람들의 거리를 저장한 배열을 순환하면서 값을 비교하면 된다 ~~~!

(설명을 못해서 또 예시를 들기)

대강 이렇게 3명의 사람이 있고, 각각의 레이더망까지 거리가 이렇다고하자

번호	레이더A까지 거리	레이더B까지 거리
1	5.14	2.40
2	170.29	95.98
3	150.32	4.23

1. a^2 = 198, b^2 = 2
   a범위안에 속하는 사람 : 1, 2, 3
   b범위안에 속하는 사람 : x

2. a^2 = 100, b^2 = 100
   a범위안에 속하는 사람 : 1
   b범위안에 속하는 사람 : 1, 2, 3

소스코드

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

public class jung1225_사람감시 {
	static final float PI = 3.141f;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine().trim()); // 감시해야 하는 사람 수
		StringTokenizer st = new StringTokenizer(br.readLine());
		float rx1 = Float.parseFloat(st.nextToken()); // 레이더1
		float ry1 = Float.parseFloat(st.nextToken());
		float rx2 = Float.parseFloat(st.nextToken()); // 레이더2
		float ry2 = Float.parseFloat(st.nextToken());
		float K = Float.parseFloat(st.nextToken()); // 감시망의 넓이
		// 원의 넓이 = PI * r * r
		// PI*r1*r1 + PI*r2*r2 = K 가 되어야하니까
		// r1*r1 + r2*r2 = K/PI
		float dist[][] = new float[N][2];
		float sumOfR = K / PI;
		// 감시해야하는 사람의 위치를 입력받아 dist에 저장
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			float x = Float.parseFloat(st.nextToken());
			float y = Float.parseFloat(st.nextToken());
			dist[i][0] = getDist(rx1, ry1, x, y); // c^2값이 있음
			dist[i][1] = getDist(rx2, ry2, x, y);
		}

		float key = sumOfR * 0.001f;

		int min = N;
		float kr1 = 0, kr2 = sumOfR;
		while (true) {
			kr1 += key;
			kr2 -= key;
			if (kr2 < 0)
				break;
			int cnt = 0;
			for (int i = 0; i < dist.length; i++) {
				if (dist[i][0] <= kr1 || dist[i][1] <= kr2) // 둘다 속하는 경우
					cnt++;
			}
			min = Math.min(min, N - cnt); // 최소인원 수 갱신
		}
		System.out.println(min);
	}

	private static float getDist(float rx, float ry, float x, float y) {
		// a^2 + b^2 = c^2
		float xv = rx - x;
		float yv = ry - y;
		return xv * xv + yv * yv;
	}
}