maximum shortest distance

maximum shortest distance

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 60 Accepted Submission(s): 27

Problem Description There are n points in the plane. Your task is to pick k points (k>=2), and make the closest points in these k points as far as possible.

Input For each case, the first line contains two integers n and k. The following n lines represent n points. Each contains 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 to two decimal places.

Sample Input 3 2 0 0 10 0 0 20

Sample Output 22.36

Author alpc50

Source 2010 ACM-ICPC Multi-University Training Contest（15）——Host by NUDT

Recommend zhouzeyong

/*
题意：给出n个点，现在让你选k个点，这k个点中，最近的两个点的距离最大

初步思路：刚好做到最大团这里，转化成最大团问题，二分，用二分的距离建边，比这条边长的两点才连线

#wa了一发：为啥double等于的时候 用减法判断开1e-6就不对，1e-8就对
*/
#include<bits/stdc++.h>
#define eps 1e-8
using namespace std;
/***********************************最大团模板************************************/
struct MAX_CLIQUE {
    static const int N=;

    bool G[N][N];//存储图
    int n;//图的定点数
    int Max[N];//保存每个节点为根节点搜索到的最大团的定点数
    int Alt[N][N];//用来存储第i层的节点
    int    ans;//用来存储最大团的定点数

    bool DFS(int cur, int tot) {//cur表示当前层数的顶点数 tot表示搜索到的当前层数
        if(cur==) {//不能扩展了就停止
            if(tot>ans) {
                ans=tot;
                return ;
            }
            return ;
        }
        for(int i=; i<cur; i++) {
            if(cur-i+tot<=ans) return ;//剪枝如果子图的节点数 加上 所有的定点数加上当前的层数 小于 前面找到的最大团

            int u=Alt[tot][i];
            if(Max[u]+tot<=ans) return ;

            int nxt=;
            for(int j=i+; j<cur; j++)
                if(G[u][Alt[tot][j]])
                    Alt[tot+][nxt++]=Alt[tot][j];

            if(DFS(nxt, tot+)) return ;
        }
        return ;
    }

    int MaxClique(){
        ans=, memset(Max, , sizeof Max);
        for(int i=n-; i>=; i--) {
            int cur=;
            for(int j=i+; j<n; j++)
                if(G[i][j])
                    Alt[][cur++]=j;
            DFS(cur, );
            Max[i]=ans;
        }
        return ans;
    }
};
struct Point{
    int x,y;
    Point(){}
    Point(int a,int b){
        x=a;
        y=b;
    }
    void input(){
        scanf("%d%d",&x,&y);
    }
    double dis(Point b){
        return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y));
    }
};
MAX_CLIQUE fuck;
Point p[];
/***********************************最大团模板************************************/
void build(double r){
    for(int i=;i<fuck.n;i++){
        for(int j=;j<fuck.n;j++){
            if(p[i].dis(p[j])-r>=eps)
                fuck.G[i][j]=;
            else fuck.G[i][j]=;
        }
    }
}
int k;

int main(){
    // freopen("in.txt","r",stdin);
    while(scanf("%d%d",&fuck.n,&k)!=EOF){
        for(int i=;i<fuck.n;i++){
            p[i].input();
        }
        double l=0.0,r=20000.0;
        while(r-l>eps){
            double m=(l+r)/2.0;
            build(m);
            if(fuck.MaxClique()>=k)//满足
                l=m;
            else r=m;
        }
        printf("%.2lf\n",l);
    }
    return ;
}