HDU 2295

二分答案+重复覆盖。注意返回的条件哦，不能光套模板。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn=3600;
const int maxc=55;
const int maxr=55;
const int inf=0x3f3f3f3f;
const double rinf=1e10;
int L[maxn], R[maxn], D[maxn], U[maxn], C[maxn];
int S[maxc], H[maxr], size;
int N,M,K;
struct City{
	double x,y;
}cities[maxr];
struct Radar{
	double x,y;
}radar[maxc];
double map[55][55];
///²»ÐèÒªSÓò
void Link(int r, int c)
{
    S[c]++; C[size]=c;
    U[size]=U[c]; D[U[c]]=size;
    D[size]=c; U[c]=size;
    if(H[r]==-1) H[r]=L[size]=R[size]=size;
    else {
        L[size]=L[H[r]]; R[L[H[r]]]=size;
        R[size]=H[r]; L[H[r]]=size;
    }
    size++;
}
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=U[c]; i!=c; i=U[i])
        L[R[i]]=R[L[i]]=i;
}
int h(){///Óþ«È·¸²¸ÇÈ¥¹ÀËã¼ôÖ¦
    int ret=0;
    bool vis[maxc];
    memset (vis, false, sizeof(vis));
    for (int i=R[0]; i; i=R[i])
    {
        if(vis[i])continue;
        ret++;
        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 ret;
}
 
int ans;
bool Dance(int k){
	int t=h();                //¸ù¾Ý¾ßÌåÎÊÌâÑ¡ÔñÏÞÖÆËÑË÷Éî¶È»òÖ±½ÓÇó½â¡£  A*Ëã·¨£¬´Ë´¦Ö»Çó×îÓŽâ
    if(k+t>K) return false;
    if(!R[0]){
        return true;
    }
    int c=R[0];
    for (int i=R[0]; i; i=R[i])
        if(S[i]<S[c])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(Dance(k+1)) return true;
        for (int j=L[i]; j!=i; j=L[j])
            resume(j);
        resume(i);
    }
    return false;
}
 
void initL(int x){///col is 1~x,row start from 1
//	ans=inf;
    for (int i=0; i<=x; ++i){
        S[i]=0;
        D[i]=U[i]=i;
        L[i+1]=i; R[i]=i+1;
    }///¶ÔÁбíÍ·³õʼ»¯
    R[x]=0;
    size=x+1;///ÕæÕýµÄÔªËØ´Óm+1¿ªÊ¼
    memset (H, -1, sizeof(H));
    ///markÿ¸öλÖõÄÃû×Ö
}

double dist(int i,int j){
	return sqrt((radar[i].x-cities[j].x)*(radar[i].x-cities[j].x)+(radar[i].y-cities[j].y)*(radar[i].y-cities[j].y));
}

void BuildLink(double r){
	for(int i=1;i<=M;i++){
		for(int j=1;j<=N;j++){
			if(map[i][j]<=r)
			Link(i,j);
		}
	}
}

void bin(){
	double Ans;
	double l=0,r=2000.0,m;
	ans=inf;
	while(l+1e-8<=r){
		double m=(l+r)/2;
		ans=inf;
		initL(N);
		BuildLink(m);
		if(Dance(0))
		{ Ans=m; r=m; }
		else l=m;
	}
	printf("%.6lf
",Ans);
}


int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&N,&M,&K);
		for(int i=1;i<=N;i++)
		scanf("%lf%lf",&cities[i].x,&cities[i].y);
		for(int j=1;j<=M;j++){
			scanf("%lf%lf",&radar[j].x,&radar[j].y);
		}
		for(int i=1;i<=M;i++){
			for(int j=1;j<=N;j++)
			map[i][j]=dist(i,j);
		}
		bin();
	}
	return 0;
}