Airport
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1534 Accepted Submission(s): 486
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
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
Case #2: 4
题意：就是给你一系列点，让你挑k个点建造飞机场，然后求剩下点到最近的飞机场的最小的最大距离；距离定义：dij = |xi - xj| + |yi - yj|
我的思路是分别找出每个点到剩下点的距离，然后sort排序，找出每个城市第k大值的最小值；
大婶们说这是DLX可重复覆盖：
下面是大神的说法：
HDU 2295 Radar（DLX可重复覆盖）差不多，我们的做法就是
保存n个城市之间的距离，sort一下，二分结果，对满足条件的DLX求覆盖程度，
求出最大距离最小值。此题二分0~INF也可解决。
http://www.2cto.com/kf/201412/364538.html
先把我的wa代码扔着，抽空补上。。。
wa代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
const int MAXN=1e5+10;
int a[65][65];
int cmp(int a,int b){
return a>b;
}
struct Node{
int x,y;
};
Node dt[65];
int getl(Node a,Node b){
return abs(a.x-b.x)+abs(a.y-b.y);
}
int main(){
int T,N,K,kase=0;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&K);
for(int i=0;i<N;i++){
scanf("%d%d",&dt[i].x,&dt[i].y);
}
for(int i=0;i<N;i++)for(int j=0;j<N;j++){
a[i][j]=getl(dt[i],dt[j]);
}
for(int i=0;i<N;i++)sort(a[i],a[i]+N,cmp);
/* for(int i=0;i<N;i++){
for(int j=0;j<N;j++)printf("%d ",a[i][j]);
puts("");
}*/
int mx=0x3f3f3f3f;
for(int i=0;i<N;i++)mx=min(mx,a[i][K-1]);
printf("Case #%d: %d\n",++kase,mx);
}
return 0;
}