输入
输入由几个测试用例组成。输入的第一行由一个整数t组成，表示测试用例的数量。每个测试用例的第一行由3个整数组成：n、m、k，代表城市数量、雷达站数量和操作员数量。以下n条线中的每一条都由城市坐标组成。
最后的M线都由一个雷达站的坐标组成。
所有坐标用一个空格分隔。
产量
对于每个测试用例，在一行上输出半径，四舍五入为六位小数。
思路；雷达的半径用二分法求出，用搜索来检验当前雷达的半径下能否覆盖全部城市，用dlx模板优化搜索，dlx模板需要一些变化。
代码：
#include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> #include <iostream> #define mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f using namespace std; const int maxm = 3010; const double ep =1e-8; int k; struct{ int n,m; int left[maxm],right[maxm],up[maxm],down[maxm],col[maxm],row[maxm]; int head[55],ans[55]; int ansed,size; void init(int _n,int _m) { n=_n; m=_m; for(int i=0;i<=m;i++) { ans[i]=0; up[i]=i; down[i]=i; left[i]=i-1; right[i]=i+1; col[i]=i; row[i]=0; } left[0]=m; right[m]=0; size=m; memset(head,-1,sizeof(head)); return ; } void insert(int r,int c) { size++; ans[c]++; down[size]=down[c]; up[size]=c; up[down[c]]=size; down[c]=size; row[size]=r; col[size]=c; if(head[r]<0) { head[r]=size; left[size]=right[size]=size; } else { left[size]=head[r]; right[size]=right[head[r]]; left[right[head[r]]]=size; right[head[r]]=size; } return ; } void delet(int c)//只删除一列 { for(int i=down[c];i!=c;i=down[i]) { left[right[i]]=left[i]; right[left[i]]=right[i]; } } void reback(int c) { for(int i=up[c];i!=c;i=up[i]) { left[right[i]]=right[left[i]]=i; } } bool ve[maxm]; int f()//还需要多少个操纵人员 { int js=0; for(int i=right[0];i!=0;i=right[i]) { ve[i]=true; } for(int c=right[0];c!=0;c=right[c]) { if(ve[c]) { js++; ve[c]=false; for(int i=down[c];i!=c;i=down[i]) { for(int j=right[i];j!=i;j=right[j]) { ve[col[j]]=false; } } } } return js; } bool dancing(int dep) { if(dep+f()>k)//剪枝 { return false; } if(right[0]==0) { return dep<=k; } int c=right[0]; for(int i=right[0];i!=0;i=right[i]) { if(ans[i]<ans[c]) { c=i; } } for(int i=down[c];i!=c;i=down[i]) { delet(i); for(int j=right[i];j!=i;j=right[j]) { delet(j); } if(dancing(dep+1)) { return true; } for(int j=left[i];j!=i;j=left[j]) { reback(j); } reback(i); } return false; } }dlx; struct node { int x,y; void inp() { scanf("%d %d",&x,&y); } }; node city[55],station[55]; double dis(node a,node b)//求距离 { return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y)); } int main() { int n,m,t; scanf("%d",&t); while(t--) { scanf("%d %d %d",&n,&m,&k); for(int i=0;i<n;i++) { city[i].inp(); } for(int i=0;i<m;i++) { station[i].inp(); } double l=0,r=1e8; while(r-l>=ep)//二分 { double mid=(l+r)/2; dlx.init(m,n); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(dis(city[j],station[i])<mid-ep)//如果雷达能覆盖城市，则插入 { dlx.insert(i+1,j+1); } } } if(dlx.dancing(0)) { r=mid-ep; } else { l=mid+ep; } } printf("%.6lf\n",l); } }