anarc 2009, poj 3996- 사람감시 > 문제은행 : 정보올림피아드&알고리즘



1225 : 사람감시

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
119 회   
시도횟수
607 회   

문제

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

Hint!

문제를 풀기 위해 원주율을 사용할 경우 원주율 값은 3.141 이라고 가정한다. 다음은 예시의 답을 그림으로 나타낸 예다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP