F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Airport

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2916    Accepted Submission(s): 937

Problem Description
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.

Input
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.

Output
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
2
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

Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2023 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2023-06-01 00:01:26, Gzip enabled Administration