Description：

从 $(1,1)$ 走到 $(n,m)$ ，不能离开以这两个点为端点的矩形，有 $k$ 个怪兽，找一条路径离怪兽距离的最小值最大。

$1\leqslant n\leqslant 3000$

Solution：

题目可以转化为给你 $k$ 个圆，为他们确定一个最大的半径，把相交的圆连起来，把和边界相连分别和 $S$ 和 $T$ 连，使得 $S$ 和 $T$ 没有被连起来，所以只要两两连边，边权为两点距离 $/2$ ，每个点和边界连长为距离的边，做 $kruskal$ ，加到 $S$ 和 $T$ 联通时的边权就是答案。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 3010

int p,n,m;

struct edges

{

	int u,v;

	double d;

}es[MAXN * MAXN];

int en = 0;

int x[MAXN],y[MAXN];

double dis(int a,int b)

{

	return sqrt(double(x[a] - x[b]) * double(x[a] - x[b]) + double(y[a] - y[b]) * double(y[a] - y[b]));

}

bool cmp_d(edges a,edges b){return a.d < b.d;}

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int main()

{

	scanf("%d%d%d",&p,&n,&m);

	for(int i = 1;i <= p;++i)

		scanf("%d%d",&x[i],&y[i]);

	for(int i = 1;i <= p;++i)

		for(int j = 1;j < i;++j)

			es[++en] = (edges){i,j,dis(i,j) / 2};

	int s = p + 1,t = p + 2;

	for(int i = 1;i <= p;++i)

	{

		es[++en] = (edges){i,s,(double)min(n - x[i],y[i] - 1)};

		es[++en] = (edges){i,t,(double)min(x[i] - 1,m - y[i])};

	}

	sort(es + 1,es + 1 + en,cmp_d);

	for(int i = 1;i <= t;++i)f[i] = i;

	for(int i = 1;i <= en;++i)

	{

		if(find(es[i].u) != find(es[i].v))

		{

			f[find(es[i].u)] = find(es[i].v);

			if(find(s) == find(t))

			{

				printf("%.2lf\n",es[i].d);

				break;

			}

		}

	}

	return 0;

}