Preparing NOJ


1500ms 0K


The country of jiuye composed by N cites. Each city can be viewed as a point in a two- dimensional plane with integer coordinates (x,y). The distance between city i and city j is defined by dij = |xi - xj| + |yi - yj|. jiuye want to setup airport in K cities among N cities. So he need your help to choose these K cities, to minimize the maximum distance to the nearest airport of each city. That is , if we define di(1 ≤ i ≤ N ) as the distance from city i to the nearest city with airport. Your aim is to minimize the value max{di|1 ≤ i ≤ N }. You just output the minimum.


The first line of the input is T (1 ≤ T ≤ 100), which stands for the number of test cases you need to solve.

The first line of each case contains two integers N ,K (1 ≤ N ≤ 60,1 ≤ K ≤ N ),as mentioned above.

The next N lines, each lines contains two integer xi and yi (-109 ≤ xi, yi ≤ 109), denote the coordinates of city i.


For each test case, print a line “Case #t: ”(without quotes, t means the index of the test case) at the beginning. Then a single integer means the minimum.

Sample Input:

3 2
0 0
4 0
5 1
4 2
0 3
1 0
3 0
8 9

Sample Output:

Case #1: 2
Case #2: 4



Provider HDU

Origin 2014 ACM/ICPC Asia Regional Shanghai Online

Code HDU5046


Submitted 0

Passed 0

AC Rate 0%

Date 08/17/2021 11:58:53


Nothing Yet