HDU3585-二分+最大团

秒速五厘米 2022-07-10 11:58 131阅读 0赞

# maximum shortest distance #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 1819    Accepted Submission(s): 609**

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

**题目大意：**

给你n个点要你求k个点中最近的点的距离的最大值

**题目思路：**

首先我们可以考虑k个点，如果我们去枚举所有的组合那么这样必然超时，然后我们可以往二分上面想，我们知道满足二分的条件是找到一种单调的关系，我们可以想到对于当前二分的值拿去把原图重新建过，如果两点之间的距离不小于该值则建边（其实这是二分的一般套路），我们知道对于改图中最小的边必然是最靠近我们二分的这个值，但是题目要满足k个点，对于重新建的这个是否是不小于k个点，我们就可以利用最大团算法，如果最大团不小于k说明对于该二分的值成立，然后我们继续二分，这里我们很好想到对于重新建的图的边肯定是和二分的值成正比的，所以这里存在单调的关系，也就是我们二分的思想成立！但是对于这题如我们不加优化很容易超时的，我们必须用较优的最大团算法才能过这题，还有二分时我们不需要去二分double，因为每个点对之间的距离都是已知的所以我们可以把所有的距离存起来排序然后二分下标！

**AC代码：**

#include<algorithm>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    const int maxn = 65;
    int n,k,num,cnt;
    double dis[maxn][maxn],p[maxn][2],all[maxn*maxn];
    int mp[maxn][maxn],dp[maxn],now[maxn];
    
    double cal(double x1,double x2,double y1,double y2){
        return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
    
    
    void dfs(int deep,int x){
        if(deep+dp[x]<=num||deep+n-x+1<=num||num>=k)return ;  //dp优化的最大团算法
        int able=0;
        int tnow[maxn];
        for(int i=x;i<=n;i++){
            tnow[i]=now[i];
            if(now[i])able++;
        }
        if(able+deep<=num)return ;
    
        for(int i=x;i<=n;i++){
            if(!tnow[i])continue;
            if(dp[i]+deep<=num)return ;
            for(int j=x;j<=n;j++)
                now[j]=tnow[j]&mp[i][j];
            dfs(deep+1,i);
        }
        if(deep>num)num=deep;
    }
    
    bool isok(double mid){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)if(i!=j){
                if(dis[i][j]>=mid)mp[i][j]=1;       //每次二分的值重新建图
                else mp[i][j]=0;
            }
        dp[n]=num=1;
        for(int i=n-1;i>=1;i--){
            for(int j=1;j<=n;j++)now[j]=mp[i][j];
            dfs(1,i+1);
            dp[i]=num;
            if(num>=k)return true;
        }
        return false;
    }
    
    int main()
    {
        while(~scanf("%d%d",&n,&k)){
            cnt=0;
            for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i][0],&p[i][1]);
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)if(i!=j)
                dis[i][j]=cal(p[i][0],p[j][0],p[i][1],p[j][1]),all[cnt++]=dis[i][j];
            sort(all,all+cnt);                //最所有距离排序去重
            cnt=unique(all,all+cnt)-all;
            int l=0,r=cnt-1,mid,ans=0;
            while(r>=l){            //二分数组下标
                mid = (l+r)/2;
                if(isok(all[mid])){
                    l=mid+1;
                    ans=mid;
                }else r=mid-1;
            }
            printf("%.2lf\n",all[ans]);
        }
        return 0;
    }