bzoj 3007 拯救小雲公主

​​http://www.elijahqi.win/archives/3705​​​

Description

英雄又即将踏上拯救公主的道路……

這次的拯救目标是——愛和正義的小雲公主。

英雄來到boss的洞穴門口，他一下子就懵了，因為面前不隻是一隻boss，而是上千隻boss。當英雄意識到自己還是等級1的時候，他明白這就是一個不可能完成的任務。

但他不死心，他在想，能不能避開boss去拯救公主呢，嘻嘻。

Boss的洞穴可以看成一個矩形，英雄在左下角（1,1），公主在右上角（row，line）。英雄為了避開boss，當然是離boss距離越遠越好了，是以英雄決定找一條路徑使到距離boss的最短距離最遠。

Ps:英雄走的方向是任意的。

你可以幫幫他嗎？

當英雄找到了美麗漂亮的小雲公主，立刻就被boss包圍了！！！英雄緩閉雙眼，舉手輕揮，白光一閃後使用了回城卷軸，回到了城堡，但隻有小雲公主回去了……因為英雄忘了進入回城的法陣了。

Input

第一行，輸入三個整數，n表示boss的數目，row，line表示矩形的大小；

接下來n行，每行分别兩個整數表示boss的位置坐标。

Output

輸出一個小數，表示英雄的路徑離boss的最遠距離，精确到小數點後兩位。

Sample Input

1 3 3

2 2

輸出樣例1：

1.00

輸入樣例2：

1 3 3

3 1

輸出樣例2：

2.00

Sample Output

HINT

100%資料，n<=3000；

#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define eps 1e-3
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*f;
}
const int N=3e3+10;
int fa[N],n,line,row;double x[N],y[N];
inline int find(int x){
    while(x!=fa[x]) x=fa[x]=fa[fa[x]];return x;
}
inline void merge(int x,int y){
    if (find(x)!=find(y)) fa[find(x)]=find(y);
}
inline double sqr(double x){return x*x;}
inline bool check(double mid){
    for (int i=1;i<=n;++i){
        if (mid>=row-x[i]||mid>=y[i]-1) merge(0,i);
        if (mid>=x[i]-1||mid>=line-y[i]) merge(i,n+1);
        for (int j=1;j<i;++j){
            if (find(i)==find(j)) continue;
            if (sqr(x[i]-x[j])+sqr(y[i]-y[j])<=4*mid*mid) merge(i,j);
        }
    }return find(0)==find(n+1);
}
int main(){
    freopen("bzoj3007.in","r",stdin);
    n=read();row=read();line=read();
    for (int i=1;i<=n;++i) x[i]=read(),y[i]=read();
    double l=0,r=min(row,line);
    while(fabs(r-l)>eps){
        for (int i=0;i<=n+1;++i) fa[i]=i;
        double mid=(l+r)/2;
        if(check(mid)) r=mid;else l=mid;
    }printf("%.2f\n",r);
    return 0;
}