Informatica Online Judge

  커피 중심지 [2275 / 08E3]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 8   Total Tried : 9


The Champion of this Problem (C++) : gs17044 - ms / 1014byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

현성이가 사는 동네에는 커피 전문점이 매우 많이 있다. 5년 전에는 커피 전문점이 1개밖에 없었지만, 그 사이에 벌써 20개나 생겼다. 사람들은 점점 커피에 중독되고, 커피를 마시기 위해 커피 전문점에 가기 때문에 커피 전문점은 계속 수가 늘어난다.

현성이는 근처에 커피 전문점이 많은 곳으로 이사가려고 부동산에 방문했다. 부동산에 있는 지도에는 모든 커피 전문점의 위치가 표시되어 있다. 상근이는 모닝 커피를 마시기 위해 m블럭만큼 걸어 나갈 수 있다. 이 때, m블럭 내에 가장 많은 커피 전문점이 있는 곳의 위치를 구하는 프로그램을 작성하시오.

현성이네 동네는 정사각형 격자 모양이고, 모든 블럭은 북-남, 동-서 축에 정렬되어져 있다. 사거리 (a,b)와 (c,d) 사이의 거리는 |a-c| + |b-d| 이다.

Input

입력의 첫 째 줄에는 dx, dy, n, q가 주어진다. 도시의 크기는 dx × dy (1 ≤ dx, dy ≤ 1000)이고, 이 도시에 있는 커피 전문점의 수는 n (0 ≤ n ≤ 5·105), 쿼리의 수는 q (1 ≤ q ≤ 20) 이다.

다음 n개 줄에는 두 정수 xi와 yi (1 ≤ xi ≤ dx, 1 ≤ yi ≤ dy) 가 주어진다. 두 정수는 i번째 커피 전문점의 위치를 나타낸다. 한 사거리에 있는 커피 전문점의 수는 최대 1개이다.

다음 q개 줄에는 정수 m이 한 줄에 하나씩 주어진다. m은 상근이가 모닝 커피를 사러 걸어나갈 수 있는 블럭의 최대 개수이다.

Output

한 쿼리당 한 줄씩 정답을 출력한다. 입력으로 주어진 각 쿼리 m마다, m블럭 내에 가장 많은 커피 전문점이 있는 곳의 위치를 출력한다.

예를 들어, 예제 출력은 (3,4)에서 1블럭 내에 커피 전문점이 3개, (2,2)에서 2블럭 내에 커피 전문점이 4개, (3,1)에서 4블럭 내에 커피 전문점이 5개 있다는 뜻이다.

만약, 가능한 위치가 여러개라면, 가장 남쪽에 있는 위치 (y좌표가 작은 것)을 출력한다. 그래도 여러개인 경우에는 가장 서쪽에 있는 위치 (x좌표가 작은 것)을 출력한다.

IO Example

입력
4 4 5 3
1 1
1 2
3 3
4 4
2 4
1
2
4

출력
3 (3,4)
4 (2,2)
5 (3,1)

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