3007: 解救小云公主
Time Limit: 5 Sec Memory Limit: 512 MBSubmit: 159 Solved: 71
[Submit][Status][Discuss]
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
2 2
输出例子1：
1.00
输入例子2：
1 3 3
3 1
输出例子2：
2.00
Sample Output
HINT
100%数据。n<=3000；
思路不错的一道题。
随意两个圆之间连边，长度为圆心距的一半。
然后问题转化为，从左上两条边到右下两条边找一条路径。使得路径上的最大边最小。SPFA。
注意ans的初值是圆心到起点和终点距离的最小值。(详见程序)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 3005
using namespace std;
int n,nx,ny,s,t;
double ans,dis[maxn],g[maxn][maxn];
bool inq[maxn];
struct data{int x,y;}a[maxn];
const double inf=1e10;
queue<int> q;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline double getdis(data a,data b)
{
double x=a.x-b.x,y=a.y-b.y;
return sqrt(x*x+y*y);
}
inline void spfa()
{
F(i,1,t) dis[i]=inf;
dis[s]=0;inq[s]=true;q.push(s);
while (!q.empty())
{
int x=q.front();q.pop();inq[x]=false;
F(i,1,t) if (x!=i&&max(dis[x],g[x][i])<dis[i])
{
dis[i]=max(dis[x],g[x][i]);
if (!inq[i]) inq[i]=true,q.push(i);
}
}
}
int main()
{
n=read();nx=read();ny=read();
s=n+1;t=n+2;
F(i,1,n) a[i].x=read(),a[i].y=read();
F(i,1,n) g[s][i]=g[i][s]=min(a[i].x-1,ny-a[i].y),g[i][t]=g[t][i]=min(a[i].y-1,nx-a[i].x);
F(i,1,n) F(j,i,n) g[i][j]=g[j][i]=getdis(a[i],a[j])/2;
ans=inf;
F(i,1,n) ans=min(ans,getdis(a[i],(data){1,1})),ans=min(ans,getdis(a[i],(data){nx,ny}));
g[s][t]=g[t][s]=min(nx-1,ny-1);
spfa();
ans=min(ans,dis[t]);
printf("%.2lf
",ans);
}