시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 125 22 18 25.714%

문제

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

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

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 도시를 나타낸다.

테스트 케이스의 첫 째 줄에는 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은 상근이가 모닝 커피를 사러 걸어나갈 수 있는 블럭의 최대 개수이다.

마지막 테스트 케이스의 다음 줄에는 0이 네 개 주어진다.

출력

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

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

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

예제 출력 형식을 참고한다.

예제 입력

4 4 5 3
1 1
1 2
3 3
4 4
2 4
1
2
4
0 0 0 0

예제 출력

Case 1:
3 (3,4)
4 (2,2)
5 (3,1)

힌트

출처

ACM-ICPC > World Finals > 2011 World Finals E번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: corea