jisoo

简单的二分

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,m;
struct po{
    int x;
    int y;
}p[1005];
int x,y;
int r[1005];
bool cmp(po x,po j){
    return x.x<j.x;
}
double l,rr,mid;
double ans;
double dis[1005][1005];
int vis[1005];
bool dfs(int x,double mid){
    //cout<<x<<endl;
    if((n-p[x].x)*2<=mid){
        return 1;
    }else{
        for(int i=1;i<=m;++i){
            if(dis[x][i]<=mid&&i!=x&&!vis[i]){
                vis[i]=1;
                if(dfs(i,mid)) return 1;
            }
        }
        return 0;
    }
    return 0;
}
bool check(double aim){
    if(aim>=p[1].x&&aim>=(n-p[m].x)){
        for(int i=1;i<=m;++i){
            if(p[i].x>aim)
            break;
            if(vis[i]) continue;
            vis[i]=1;
            if(dfs(i,aim*2))
                return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&p[i].x,&p[i].y); 
    }
    rr=n;
//  for(int i=1;i<=m;++i){
//      cout<<r[i]<<endl;
//  }
    sort(p+1,p+m+1,cmp);
    for(int i=1;i<=m;++i){
        for(int j=i+1;j<=m;++j){
            double di=(double)sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
            dis[i][j]=dis[j][i]=di;
        }
    }
    while(l+1e-6<=rr){
        mid=(l+rr)/2; 
        if(check(mid)){
            rr=mid;
            ans=mid;
        } else{
            l=mid;
        }
        memset(vis,0,sizeof(vis));
    }
    printf("%.2lf",ans);
    return 0;
}