AT_abc181_f 题解

· · 题解

题目传送门

思路

可以使用并查集和二分解决此题。

首先发现答案具有单调性，这是因为大的圈一定能包含小的圈。于是可以二分圈的半径 r，难点在于二分的判断函数。

只要满足 2\times r\le\operatorname{dis}(X,Y)，则半径为 r 的圆可以穿过 X 点和 Y 点。不难想到可以将所有的点全部连接起来。做两层循环的枚举，若 i 点和 j 点满足要求，就将它们连通起来。可以使用并查集进行处理。

然后处理上下边界，将能到达上下边界的点与 L 和 R 相连（L 和 R 为自定义的上下边界的点），最后判断 L 和 R 是否连通即可。

注意事项

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=100+10,L=101,R=102;
const double EPS=1e-13;
int n,x[N],y[N],fa[N];
void _init(){
    for(int i=0;i<N;++i)
        fa[i]=i;
    return;
}
int _find(int x){
    if(x==fa[x])
        return x;
    fa[x]=_find(fa[x]);
    return fa[x];
}
void _merge(int x,int y){
    int xx=_find(x),yy=_find(y);
    if(xx!=yy)
        fa[xx]=yy;
    return;
}
#define y1 y_1
int calc(int x1,int x2,int y1,int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
bool check(double r){
    _init();
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j)
            if(4*r*r>calc(x[i],x[j],y[i],y[j]))
                _merge(i,j);
        if(100-y[i]<=2*r)
            _merge(i,L);
        if(y[i]+100<=2*r)
            _merge(i,R);
    }
    return _find(L)!=_find(R);
}
int main(){
    n=read();
    for(int i=1;i<=n;++i)
        x[i]=read(),y[i]=read();
    double l=0,r=100;
    while(abs(l-r)>=EPS){
        double mid=(l+r)/2;
        if(check(mid))
            l=mid;
        else r=mid;
    }
    printf("%.12lf\n",r);
    return 0;
}