Informatica Online Judge

  커피 숍세권 [2302 / 08FE]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 3   Total Tried : 5


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

[ACM ICPC 2011 WF]

Background

잠깐의 유행일까 계속될까? 확실하지 않지만, 지역에서 오픈하는 커피숍들의 개수가 점점 늘어나는 것처럼 보인다. 하지만 확실한 것은 사람들이 커피를 즐기면 즐길수록 커피숍 주변의 아파트 월세가 높아질 것이다.

이러한 상황은 지역 부동산 업계의 관심을 불러일으켰다. 부동산 업자들은 주변에 있는 커피숍들의 개수를 중심으로 가장 비싼 아파트 위치가 어디일지에 대해서 궁금증을 가지게 되었다.

커피숍들의 위치가 표시된 지도 정보를 받았다. 매일 아침에 사람들은 아파트 근처에 있는 커피숍들로 걸어가는데 몇 블록 이내에 있는 커피숍들만 방문할 수 있다.

도시의 도로들은 동서남북으로 연결되는 격자형 길로 구성되어있기 때문에, 어떤 위치 (a, b)에서 다른 위치 (c, d)로 걸어서 이동하는데 필요한 거리는 |a-c|+|b-d|가 된다.

가장 많은 커피숍으로 이동할 수 있는 가장 비싼 아파트의 위치를 찾아보자.

Input

도시의 지도 정보가가 포함되어있는 여러 개의 데이터가 순서대로 입력된다.

각 데이터의 첫 번째 줄에는 도시의 동서 방향 너비(dx), 남북 방향 너비(dy), 커피숍의 개수(n), 쿼리 개수(q) 가 공백을 두고 한 줄로 입력된다.

그 다음 n개의 줄에는 각 i번째 커피숍의 정수 위치 좌표(xi, yi)가 줄을 바꿔 입력되고, 같은 좌표의 커피숍은 없다.

그 다음 q개의 줄에는 사람들이 커피를 먹기 위해 움직인다고 가정하는 최대 거리(m)가 q번 입력된다.

데이터가 더 이상 없는 경우에는 dx, dy, n, q 값이 0 0 0 0으로 입력된다.


[입력값의 정의역]

$1 <= dx, dy <= 1,000$
$0 <= n <= 500,000$
$1 <= q <= 20$
$1 <= x_i <= dx$
$1 <= y_i <= dy$
$0 <= m <= 10^6$

Output

케이스별로 케이스 번호를 출력하고, 이동거리가 m일 때 가장 많은 커피숍을 이동할 수 있는 아파트 위치를 커피숍 개수와 좌표로 출력한다.

입출력 예시의 첫 번째 데이터에서는 이동거리가 1일 때 주변에 3개의 커피숍으로 이동할 수 있는 아파트 좌표 (3, 4), 이동거리가 2일 때 주변 4개 좌표 (2, 2), 이동거리가 4일 때 주변 5개 좌표 (3, 1)를 의미한다.

만약, 주변에 있는 커피숍의 개수가 같은 경우에는 y좌표값이 작은 위치를 출력한다. y좌표값이 같은 경우에는 x좌표값이 작은 위치를 출력하도록 한다.

IO Example

입력예시
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)

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