问题描述 :
Is it just a fad or is it here to stay? You’re not sure, but the steadily increasing number of coffee shops that are opening in your hometown has certainly become quite a draw. Apparently, people have become so addicted to coffee that apartments that are close to many coffee shops will actually fetch higher rents.
This has come to the attention of a local real-estate company. They are interested in identifying the most valuable locations in the city in terms of their proximity to large numbers of coffee shops. They have given you a map of the city, marked with the locations of coffee shops. Assuming that the average person is willing to walk only a fixed number of blocks for their morning coffee, you have to find the location from which one can reach the largest number
of coffee shops. As you are probably aware, your hometown is built on a square grid layout, with blocks aligned on north-south and east-west axes. Since you have to walk along streets, the distance between intersections (a, b) and (c, d) is |a – c| + |b – d|.
输入:
The input contains several test cases. Each test case describes a city. The first line of each test case contains four integers dx, dy, n, and q. These are the dimensions of the city grid dx × dy (1 <= dx, dy <= 1000), the number of coffee shops n (0 <= n <= 5 × 10^5), and the number of queries q (1 <= q <= 20). Each of the next n lines contains two integers xi and yi (1 <= xi <= dx, 1 <= yi <= dy); these specify the location of the ith coffee shop. There will be at most one coffee shop per intersection. Each of the next q lines contains a single integer m (0 <= m <= 10^6), the maximal distance that a person is willing to walk for a cup of coffee.
The last test case is followed by a line containing four zeros.
输出:
The input contains several test cases. Each test case describes a city. The first line of each test case contains four integers dx, dy, n, and q. These are the dimensions of the city grid dx × dy (1 <= dx, dy <= 1000), the number of coffee shops n (0 <= n <= 5 × 10^5), and the number of queries q (1 <= q <= 20). Each of the next n lines contains two integers xi and yi (1 <= xi <= dx, 1 <= yi <= dy); these specify the location of the ith coffee shop. There will be at most one coffee shop per intersection. Each of the next q lines contains a single integer m (0 <= m <= 10^6), the maximal distance that a person is willing to walk for a cup of coffee.
The last test case is followed by a line containing four zeros.
样例输入:
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)
