bzoj 3007 拯救小云公主

bzoj 3007 拯救小云公主

​​ 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；

通过画图考虑如何会困住英雄

然后像noip2017 奶酪一样二分答案直接并查集就可以 或者bfs什么都可以

#include#include#include#include#define eps 1e-3using 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;jeps){ 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。