저격2 > 문제은행



문제은행

3359 : 저격2

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 4 회    시도횟수: 94 회   



시논(Sinon)은 게임 KGO(KOI 건 온라인)에서 유명한 저격수이다.

그녀는 이번에 열리는 KGO 최고 권위의 대회 BoK(Bullets of KOI)에 출전하였다.

이 대회의 특징은 15분마다 새틀라이트 스캔을 통해 플레이어의 좌표가 공개된다는 것이다.

플레이어의 좌표는 모두 xy평면 위에 있으므로, 좌표는 (x, y)꼴로 표현된다.

대회 도중, 스캔을 확인한 시논은 자신을 제외하고 총 N명이 현재 생존해 있다는 것을 확인하였다.

적들의 위치를 파악한 시논은 자신이 좋아하는 Q개의 저격 장소 중 하나로 적들에게 들키지 않고 저격 장소를 옮기려고 한다.

시논은 자신의 경험으로 적의 15분 동안에 움직일 수 있는 범위가 적의 위치를 중심으로 하고, 

변이 x축과 y축에 평행한 정사각형 내부(경계 포함)이라는 것을 알고 있다. 

또한, 시논은 대회에 다수 출전하여 많은 플레이어들을 만났었기 때문에 이번에 출전한 상대 플레이어들의 행동 범위의 크기도 알고 있다.

시논은 저격 장소에서 적을 마주치는 최악의 상황을 피하기 위해, 

자신의 저격 장소들 중에서 적들의 행동 범위 안에 없고 자신에게 제일 가까운(유클리드 거리로) 저격 장소를 찾고자 한다.

시논을 도와주자.​ 

 

[입력 예 1 설명]

설명 : 2번째 저격지점이 제일 가깝지만, 1번 적과 2번 적의 행동범위 안에 들어와 있다. 

1번째와 3번째 저격지점은 둘 다 시야 범위 안에 들어와 있으므로, 제일 가까운 1번이 답이다.

 




첫 번째 줄에 적의 수 N, 저격지점의 개수 Q가 주어진다.
(1 <= N <= 105, 1 <= Q <= 105)
2 ~ N+1줄에 적들의 위치, 정사각형의 변의 길이가 주어진다. 
(-108 <= xi, yi <= 108, 0 <= ri <= 2*108, ri는 짝수)
그 다음 줄에 시논의 좌표가 주어진다. 
(-108 < x,y < 108)
다음 Q개의 줄에는 시논이 좋아하는 저격 장소가 주어진다. 저격 장소의 번호는 윗줄부터 1번 ~ Q번이다.
(-108 <= x,y <= 108)



적들의 행동 범위 안에 없으면서 시논에게 제일 가까운 저격 장소의 번호를 출력한다. 
만약 거리가 같다면 번호가 제일 작은 장소를 출력한다. 만약 그러한 장소가 없다면 –1을 출력한다.

[부분 점수 제약]
(1) N, Q <= 1000 (15점)
(2) 모든 x,y,r의 절대값이 1000보다 작다. (5점)
(3) r_i = 0 (10점)
(4) N, Q <= 30000 (25점)
(5) 제약 조건 없음. (45점)


3 3
0 0 2
2 2 2
5 5 4
0 0
-2 –1
1 1
-1 3
1


2 2
0 0 0
1 1 2
0 0
0 0
2 2
-1


출처 : william202




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.