Informatica Online Judge

  저격2 #3 [2211 / 08A3]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 14   Total Tried : 14


The Champion of this Problem (C++) : gs15120 - 145ms / 2678byte
My Best Submission (C++) : N/A

[34th 박관영]
Writer ID : [gs16036]

Background

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

그녀는 이번에 열리는 GGO 최고 권위의 대회 BoG(Bullets of GSHS)에 출전하였다.
이 대회의 특징은 15분마다 새틀라이트 스캔을 통해 플레이어의 좌표가 공개된다는 것이다.

플레이어의 좌표는 모두 xy평면 위에 있으므로, 좌표는 (x, y)꼴로 표현된다.
대회 도중, 스캔을 확인한 시논은 자신을 제외하고 총 N명이 현재 생존해 있다는 것을 확인하였다.

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

시논은 자신의 경험으로 적의 15분 동안에 움직일 수 있는 범위가 적의 위치를 중심으로 하고, 변이 x축과 y축에 평행한 정사각형 내부(경계 포함)이라는 것을 알고 있다. 또한, 시논은 대회에 다수 출전하여 많은 플레이어들을 만났었기 때문에 이번에 출전한 상대 플레이어들의 행동 범위의 크기도 알고 있다.

시논은 저격 장소에서 적을 마주치는 최악의 상황을 피하기 위해, 자신의 저격 장소들 중에서 적들의 행동 범위 안에 없고 자신에게 제일 가까운(유클리드 거리로) 저격 장소를 찾고자 한다.

시논을 도와주자.

Input

첫 번째 줄에 적의 수 N, 저격지점의 개수 Q가 주어진다.(1<=N<=10^5, 1<=Q<=10^5)

2 ~ N+1줄에 적들의 위치, 정사각형의 변의 길이가 주어진다. (-10^8<=xi, yi<=10^8, 0<=ri<=2*10^8, ri는 짝수)

그 다음 줄에 시논의 좌표가 주어진다. (-10^8
다음 Q개의 줄에는 시논이 좋아하는 저격 장소가 주어진다. 저격 장소의 번호는 윗줄부터 1번 ~ Q번이다.(-10^8<=xj, yj<=10^8)

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

Output

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

IO Example

Example 1
Input)
3 3
0 0 2
2 2 2
5 5 4
0 0
-2 –1
1 1
-1 3

Output)
1

설명 : 2번째 저격지점이 제일 가깝지만, 1번 적과 2번 적의 행동범위 안에 들어와 있다. 1번째와 3번째 저격지점은 둘 다 시야 범위 안에 들어와 있으므로, 제일 가까운 1번이 답이다.

Example 2

Input)
2 3
0 0 10
6 6 0
0 0
5 5
6 6
7 7

Output)
3

Example 3

Input)
2 2
0 0 0
1 1 2
0 0
0 0
2 2

Output)
-1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]