题意：
一个row * line的矩形，英雄在左下角(1,1),公主在右上角(row,line),有n个位置是boss。英雄现在要去公主那里，但是要避开boos，英雄决定找一条路径使到距离boss的最短距离最远。雄走的方向是任意的。
问英雄的路径离boss的最远距离
题解：
不难看出是二分，我们二分距离boss的距离mid，那怎么判断呢？
有个很巧妙的方法
英雄不能去的位置就是以boss为中心，mid为半径的圆，因为有n个boss，也就是有n个园，如果这n个圆可以阻断从左下角到右上角的路，说明这个距离就是不合法的。那我们就从与左侧和上恻相交的圆开始，不断往外扩，与圆相交的就加入队列中，看是否可以扩到右侧和下恻墙壁
详细可见代码
代码：
// Problem: P2498 [SDOI2012]拯救小云公主
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2498
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Data:2021-09-08 20:04:58
// By Jozky
#include <bits/stdc++.h>
#include <unordered_map>
#define debug(a, b) printf("%s = %d\n", a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll= 1e18;
const int INF_int= 0x3f3f3f3f;
void read(){};
template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar)
{
x= 0;
char c= getchar();
bool flag= 0;
while (c < '0' || c > '9')
flag|= (c == '-'), c= getchar();
while (c >= '0' && c <= '9')
x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();
if (flag)
x= -x;
read(Ar...);
}
template <typename T> inline void write(T x)
{
if (x < 0) {
x= ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#else
startTime= clock();
freopen("in.txt", "r", stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#else
endTime= clock();
printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn= 4e5;
struct node
{
int x, y;
} a[maxn];
int dis[4000][4000];
int vis[maxn];
int n, row, line;
queue<int> q;
bool able(int d, double r)
{ //可以相交
return r * r * 4 > d;
}
bool check(double r)
{
for(int i=1;i<=n;i++)
vis[i]=0;
while (!q.empty())
q.pop();
for (int i= 1; i <= n; i++) {
if (a[i].x < r || row - a[i].y < r) { //将左侧和上侧相连的boss加入队列
q.push(i);
vis[i]= 1;
}
}
while (!q.empty()) {
int top= q.front();
q.pop();
if (line - a[top].x < r || a[top].y < r) //如果与右侧和下侧相交，则说明不合法
return 0;
for (int i= 1; i <= n; i++) {
if (!vis[i] && able(dis[top][i], r)) { //如果相交，加入队列
vis[i]= 1;
q.push(i);
}
}
}
return 1;
}
int Dis(int x, int y)
{
return (a[x].x - a[y].x) * (a[x].x - a[y].x) + (a[x].y - a[y].y) * (a[x].y - a[y].y);
}
const double eps= 1e-7;
int main()
{
rd_test();
read(n, line, row);
row--;
line--;
for (int i= 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
a[i].x--;
a[i].y--;
}
for (int i= 1; i <= n; i++) {
for (int j= i + 1; j <= n; j++) {
dis[i][j]= dis[j][i]= Dis(i, j);
}
}
double l= 0.0, r= r=min(row,line);
while (fabs(l - r) > eps) {
double mid= (l + r) / 2;
// printf("mid=%lf\n",mid);
// cout<<"mid="<<mid<<endl;
if (!check(mid))
r= mid;
else
l= mid ;
}
printf("%.2lf\n",l);
return 0;
// cout << l << endl;
//Time_test();
}
