洛谷P2498 [SDOI2012]拯救小云公主 【二分 + 并查集】

时间:2024-05-27 09:06:44

题目

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

这次的拯救目标是——爱和正义的小云公主。

英雄来到boss的洞穴门口,他一下子就懵了,因为面前不只是一只boss,而是上千只boss。当英雄意识到自己还是等级1的时候,他明白这就是一个不可能完成的任务。

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

Boss的洞穴可以看成一个矩形,英雄在左下角(1,1),公主在右上角(row,line)。英雄为了避开boss,当然是离boss距离越远越好了,所以英雄决定找一条路径使到距离boss的最短距离最远。

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

你可以帮帮他吗?

当英雄找到了美丽漂亮的小云公主,立刻就被boss包围了!!!英雄缓闭双眼,举手轻挥,白光一闪后使用了回城卷轴,回到了城堡,但只有小云公主回去了……因为英雄忘了进入回城的法阵了。

输入格式

第一行,输入三个整数,n表示boss的数目,row,line表示矩形的大小;

接下来n行,每行分别两个整数表示boss的位置坐标。

输出格式

输出一个小数,表示英雄的路径离boss的最远距离,精确到小数点后两位。

输入样例

1 3 3

2 2

输出样例

1.00

提示

数据范围:

20%数据,boss坐标范围小于等于50;

60%数据,n<=1500;

100%数据,n<=3000;

题解

如果我们将所有boss看做一个半径为r的圆,那么显然当r大到刚好封堵住左下角到右上角的道路时,这个r即为英雄距离boss的最远值

二分 + 并查集即可

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define eps 1e-4
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 3010,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
struct point{double x,y;}p[maxn];
double X,Y;
int n,pre[maxn];
double d[maxn][maxn];
inline int find(int u){return u == pre[u] ? u : pre[u] = find(pre[u]);}
inline double dis(int u,int v){
return sqrt((p[u].x - p[v].x) * (p[u].x - p[v].x) + (p[u].y - p[v].y) * (p[u].y - p[v].y));
}
bool check(double R){
for (int i = 1; i <= n + 4; i++) pre[i] = i;
for (int i = 1; i <= n; i++){
for (int j = i + 1; j <= n; j++){
if (d[i][j] <= 2 * R){
pre[find(j)] = find(i);
}
}
if (p[i].x - 1 <= R) pre[find(n + 1)] = find(i);
if (X - p[i].x <= R) pre[find(n + 2)] = find(i);
if (p[i].y - 1 <= R) pre[find(n + 3)] = find(i);
if (Y - p[i].y <= R) pre[find(n + 4)] = find(i);
}
return (find(n + 1) == find(n + 2)) || (find(n + 3) == find(n + 4)) ||
(find(n + 1) == find(n + 3)) || (find(n + 2) == find(n + 4));
}
int main(){
n = read(); X = read(); Y = read();
for (int i = 1; i <= n; i++) p[i].x = read(),p[i].y = read();
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
d[i][j] = dis(i,j);
double l = 0,r = max(X,Y),mid;
while (fabs(r - l) > eps){
mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
printf("%.2lf\n",l);
return 0;
}