사람감시 > 문제은행

본문 바로가기


실전대비 Level3

1225 : 사람감시

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 26 회    시도횟수: 161 회   



2차원 평면에 2개의 레이더와 N명의 사람이 서있다. 레이더는 자신의 위치를 중심으로 원의 형태로 감시망을 펼칠 수 있으며, 펼칠 수 있는 원의 크기는 제한이 되어있으며, 2개의 레이더가 펼치게 되는 원의 감시망의 크기는 K를 넘지 않아야 한다. 감시망은 서로 겹칠 수 있으며, 이러할 경우 겹치는 부분을 하나의 넓이로 간주하지 않는다.

 

2개의 레이더의 감시망의 넓이가 K 이하로 감시망을 펼칠 경우 감시를 하지 못하는 사람의 수를 최소화 하는 프로그램을 작성하라.


입력의 첫 번째 줄에는 감시해야 하는 사람의 수 N(1≤N≤5,000)이 입력된다.
그 다음 줄에는 첫 번째 레이더의 X, Y 좌표가 입력되고, 그 다음에는 두 번째 레이더의 X, Y 좌표가 입력되며, 마지막으로 감시망의 넓이 K 가 입력되며 0 이상이다. 각각의 좌표는 실수이다.

그 다음 줄부터 N개의 줄에는 각 사람의 X, Y 좌표가 한 줄에 하나씩 입력된다. 이들 좌표값 역시 실수이다.


감시하지 못하는 최소 사람의 수를 출력한다.

[Copy]
6 
-3 0 3 0 40.833 
-1 4 
-2 2.5 
1 2 
5 2 
-4 0 
-3 -1
[Copy]
2



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


출처 : anarc 2009


anarc 2009 Air Strike, poj 3996

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.