【玄关】玄学WA 10pts求调
查看原帖
【玄关】玄学WA 10pts求调
743014
_H17_楼主2024/8/5 17:03
#include<bits/stdc++.h>
using namespace std;
const double EPS=1e-5;
struct Boss{
    int x,y;
    Boss(int x=0,int y=0):x(x),y(y){}
    void read(){
        cin>>x>>y;
        return;
    }
}a[3001];
int n,row,line,f[3002];
double l=0,r,mid;
double dist(double a,double b){
	return a*a+b*b;
}
bool ismergable(Boss a,Boss b,double k){
    return dist(abs(a.x-b.x),abs(a.y-b.y))<=k*k*4;
}
int findfa(int u){
    return (u==f[u])?u:(f[u]=findfa(f[u]));
}
void merge(int u,int v){
	int fu=findfa(u),fv=findfa(v);
    f[fu]=fv;
}
bool check(double k){
    for(int i=0;i<=n+1;i++)
        f[i]=i;
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if(ismergable(i,j,k))
            	merge(i,j);
    for(int i=1;i<=n;i++){
        if(a[i].x-k<1||a[i].y+k>line)
            merge(0,i);
        if(a[i].y-k<1||a[i].x+k>row)
            merge(n+1,i);
    }
    return findfa(0)!=findfa(n+1);
}
int main(){
    cin>>n>>row>>line;
    r=min(row,line);
    for(int i=1;i<=n;i++)
        a[i].read();
    //getchar();
    while(l+EPS<r){
        mid=(l+r)/2;
        if(check(mid))
            l=mid;
        else
            r=mid;
        //cerr<<"sus with "<<l<<' '<<r<<'\n';
        //getchar();
    }
    cout<<fixed<<setprecision(2)<<r;
    return 0;
}
2024/8/5 17:03
加载中...