1225 : 사람감시
제한시간: 1000 ms
메모리제한: 64 MB
해결횟수: 29 회
시도횟수: 173 회
2차원 평면에 2개의 레이더와 N명의 사람이 서있다. 레이더는 자신의 위치를 중심으로 원의 형태로 감시망을 펼칠 수 있으며, 펼칠 수 있는 원의 크기는 제한이 되어있으며, 2개의 레이더가 펼치게 되는 원의 감시망의 크기는 K를 넘지 않아야 한다. 감시망은 서로 겹칠 수 있으며, 이러할 경우 겹치는 부분을 하나의 넓이로 간주하지 않는다.
2개의 레이더의 감시망의 넓이가 K 이하로 감시망을 펼칠 경우 감시를 하지 못하는 사람의 수를 최소화 하는 프로그램을 작성하라.
입력의 첫 번째 줄에는 감시해야 하는 사람의 수 N(1≤N≤5,000)이 입력된다. 그 다음 줄에는 첫 번째 레이더의 X, Y 좌표가 입력되고, 그 다음에는 두 번째 레이더의 X, Y 좌표가 입력되며, 마지막으로 감시망의 넓이 K 가 입력되며 0 이상이다. 각각의 좌표는 실수이다. 그 다음 줄부터 N개의 줄에는 각 사람의 X, Y 좌표가 한 줄에 하나씩 입력된다. 이들 좌표값 역시 실수이다.
감시하지 못하는 최소 사람의 수를 출력한다.
6 -3 0 3 0 40.833 -1 4 -2 2.5 1 2 5 2 -4 0 -3 -1 |
2 |
문제를 풀기 위해 원주율을 사용할 경우 원주율 값은 3.141 이라고 가정한다. 다음은 예시의 답을 그림으로 나타낸 예다.
출처 : anarc 2009, poj 3996