Time Limit: 2000/1000 MS(Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1879 Accepted Submission(s): 643
Problem Description
There are n points in theplane. Your task is to pick k points (k>=2), and make the closest points inthese k points as far as possible.
Input
For each case, the first linecontains two integers n and k. The following n lines represent n points. Eachcontains two integers x and y. 2<=n<=50, 2<=k<=n,0<=x,y<10000.
Output
For each case, output a line contains a real number with precision up totwo decimal places.
Sample Input
3 2
0 0
10 0
0 20
Sample Output
22.36
#include <bits/stdc++.h> using namespace std; #define mst(a,b) memset((a),(b),sizeof(a)) #define f(i,a,b) for(int i=(a);i<(b);++i) const int maxn = 55; const int mod = 9973; const int INF = 0x3f3f3f3f; const double eps = 1e-4; #define ll long long #define rush() int T;scanf("%d",&T);while(T--) bool link[maxn][maxn]; //各点间的连接关系 int dp[maxn]; //记录以i出发构成的最大团顶点数量(从i到n-1的最大团) int stk[maxn][maxn]; //第i层中与之相连的第j大的标号 int mx; //最后的结果 double dis[maxn][maxn]; struct node { int x,y; } a[maxn]; double getdis(node a,node b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } //一共有n个点，dep表示当前的层数，ns代表与当前层相连并且比ns大的标号个数 int dfs(int n,int ns,int dep) { if(ns==0) { if(dep>mx) { mx=dep; return 1; } return 0; } for(int i=0;i<ns;i++) { if(ns+dep-i<=mx) //此次优化之处 return 0; int k=stk[dep][i]; //与之相连的第i个点 if(dep+n-k<=mx) //若当前顶点数量加上还能够增加的最大数量仍小于当前最优解则退出; return 0; //若当前顶点数量加上dp[k]仍小于当前最优解则退出; if(dep+dp[k]<=mx) return 0; int cnt=0; for(int j=i+1;j<ns;j++) { int p=stk[dep][j]; //i后边的某个点 if(link[k][p]) //如果i和j相连 stk[dep+1][cnt++]=p; } if(dfs(n,cnt,dep+1)) return 1; } return 0; } int maxclique(int n) { mx=0; for(int i=n-1; i>=0; i--) { int ns=0; for(int j=i+1; j<n; j++) { if(link[i][j]) stk[1][ns++]=j; } dfs(n,ns,1); dp[i]=mx; } return mx; } int main() { int n,k; while(~scanf("%d%d",&n,&k)) { for(int i=0; i<n; i++) { scanf("%d%d",&a[i].x,&a[i].y); } for(int i=0; i<n-1; i++) for(int j=i+1; j<n; j++) { dis[i][j]=dis[j][i]=getdis(a[i],a[j]); } double l=0,r=15000; while(r-l>eps) { double m=(l+r)/2; for(int i=0;i<n-1;i++) for(int j=i+1;j<n;j++) { link[i][j]=link[j][i]=(dis[i][j]>=m); } int ans=maxclique(n); if(ans>=k) l=m; else r=m; } printf("%.2lf\n",l); } return 0; }
