Radar
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2882 Accepted Submission(s): 1113
Problem Description
N cities of the Java Kingdom need to be covered by radars for being in a state of war. Since the kingdom has M radar stations but only K operators, we can at most operate K radars. All radars have the same circular coverage with a radius of R. Our goal is to minimize R while covering the entire city with no more than K radars.
Input
The input consists of several test cases. The first line of the input consists of an integer T, indicating the number of test cases. The first line of each test case consists of 3 integers: N, M, K, representing the number of cities, the number of radar stations and the number of operators. Each of the following N lines consists of the coordinate of a city.
Each of the last M lines consists of the coordinate of a radar station.
Each of the last M lines consists of the coordinate of a radar station.
All coordinates are separated by one space.
Technical Specification
1. 1 ≤ T ≤ 20
2. 1 ≤ N, M ≤ 50
3. 1 ≤ K ≤ M
4. 0 ≤ X, Y ≤ 1000
Output
For each test case, output the radius on a single line, rounded to six fractional digits.
Sample Input
1
3 3 2
3 4
3 1
5 4
1 1
2 2
3 3
3 3 2
3 4
3 1
5 4
1 1
2 2
3 3
Sample Output
2.236068
昨天用G++交T了一下午，刚才换C++交了一发报RE了，发现是数组开小了，改后重交就过了，早知道是RE昨天就不会那么头疼了，再也不信G++。
用二分来找答案，城市作为列，每个雷达最为行，行和列的组合就是此雷达能否覆盖这个城市，每次给出一个二分数值后构造一个矩阵，然后dancing一下，如果能得到答案那么将值减小再尝试，反之加大。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <cstdio>
using namespace std; struct Node
{
double x,y;
}; const int HEAD = ;
const int SIZE = ;
int N,M,K;
double RADAR[SIZE][SIZE];
Node CITY[SIZE];
bool VIS[SIZE];
int U[SIZE * SIZE],D[SIZE * SIZE],L[SIZE * SIZE],R[SIZE * SIZE],C[SIZE * SIZE],S[SIZE * SIZE]; int comp(const void * a,const void * b);
int h(void);
void debug(int count);
void ini(void);
bool dancing(int);
void remove(int);
void resume(int); int main(void)
{
int t;
double x,y; scanf("%d",&t);
while(t --)
{
scanf("%d%d%d",&N,&M,&K);
for(int i = ;i < N;i ++)
scanf("%lf%lf",&CITY[i].x,&CITY[i].y);
for(int i = ;i < M;i ++)
{
scanf("%lf%lf",&x,&y);
for(int j = ;j < N;j ++)
RADAR[i][j] = sqrt(pow(CITY[j].x - x,) + pow(CITY[j].y - y,));
} double l = ,r = ;
double mid = ;
while(r - l > 1e-)
{
mid = (l + r) / ;
ini(); int count = N + ;
for(int i = ;i < M;i ++)
{
int first = count;
for(int j = ;j < N;j ++)
if(RADAR[i][j] <= mid)
{
R[count] = count + ;
L[count] = count - ;
U[count] = U[j + ];
D[count] = j + ; D[U[j + ]] = count;
U[j + ] = count; C[count] = j + ;
S[j + ] ++;
count ++;
}
L[first] = count - ;
if(first != count)
R[count - ] = first;
}
//debug(count );
if(dancing())
r = mid;
else
l = mid;
} printf("%lf\n",mid);
} return ;
} void ini(void)
{
R[HEAD] = ;
L[HEAD] = N;
for(int i = ;i <= N;i ++)
{
L[i] = i - ;
R[i] = i + ;
U[i] = D[i] = C[i] = i;
S[i] = ;
}
R[N] = HEAD;
} bool dancing(int k)
{
if(R[HEAD] == HEAD)
return true;
if(k + h() > K)
return false; int c = R[HEAD];
for(int i = R[HEAD];i != HEAD;i = R[i])
if(S[c] > S[i])
c = i; for(int i = D[c];i != c;i = D[i])
{
remove(i);
for(int j = R[i];j != i;j = R[j])
remove(j);
if(dancing(k + ))
return true;
for(int j = L[i];j != i;j = L[j])
resume(j);
resume(i);
} return false;
} void remove(int c)
{
for(int i = D[c];i != c;i = D[i])
{
L[R[i]] = L[i];
R[L[i]] = R[i];
}
} void resume(int c)
{
for(int i = D[c];i != c;i = D[i])
{
L[R[i]] = i;
R[L[i]] = i;
}
} void debug(int count)
{
for(int i = ;i < count;i ++)
printf("%d U:%d D:%d L:%d R:%d C:%d S:%d\n",i,U[i],D[i],L[i],R[i],C[i],S[i]);
cout << endl << endl;
} int h(void)
{
fill(VIS,VIS + SIZE,false); int count = ;
for(int i = R[HEAD];i;i = R[i])
if(!VIS[i])
{
count ++;
VIS[i] = true;
for(int j = D[i];j != i;j = D[j])
for(int k = R[j];k != j;k = R[k])
VIS[C[k]] = true;
}
return count;
}