10.15T1
T1刺客信条(AC): 这道题坑得我。。。。。。
现在背都背得到题。
这道题的意思就是，一个二维平面，有很多点，每个点都会以同一个半径形成一个圆，求最小的半径，使得存在一条从点(0,0)到点(n,m)的路径。
这道题，是我们考过的一道题的弱化版： 越狱
当时考试时就考虑到根据题意，维护上下边界的连通性，再bfs判定，若上下界联通，则必须杀人，这道题思路类似，不过bfs极易超时，所以我们通过更高效的并查集，同时维护上，下，左，右之间的连通性，判定时：
若左右或上下联通，GG。
若左上或右下联通，GG。
其余情况，就肯定有办法到达。
至于我考试的时候为什么错了，是因为当时样例给得很巧合，主角只用通过走整点就可以到达(n,m)，然而这道题不一定要走整点，所以当时直接排除了这种写法。 以后遇到题意有争议的时候，该多问问老师。
code：
#include"cstdio"
#include"cmath"
#include"algorithm"
#include"cstring"
using namespace std;
const int maxn=2010;
const int new1=2001,new2=2002,new3=2003,new4=2004;
int n,m,k;
double l,r,lef,rig,dist[maxn][maxn];
int fa[maxn];
struct xt
{
double x,y;
}peo[maxn];
int findup(int x)
{
return x==fa[x]?x:fa[x]=findup(fa[x]);
}
void mergee(int x,int y)
{
int fx=findup(x),fy=findup(y);
if(fx!=fy)
fa[fx]=fy;
}
double calc(int x,int y)
{
return sqrt(((peo[x].x-peo[y].x)*(peo[x].x-peo[y].x)+(peo[x].y-peo[y].y)*(peo[x].y-peo[y].y)));
}
int check(double x)
{
for(int i=1;i<=n;++i)
fa[i]=i;
fa[new1]=new1,fa[new2]=new2,fa[new3]=new3,fa[new4]=new4;
k=0;
for(int i=1;i<=n;++i)
{
if(peo[i].x-x<0)
mergee(i,new1);
if(peo[i].x+x>lef)
mergee(i,new2);
if(peo[i].y+x>rig)
mergee(i,new3);
if(peo[i].y-x<0)
mergee(i,new4);
for(int j=1;j<=n;++j)
{
if(i==j)
continue;
if(dist[i][j]<2.0*x)
mergee(i,j);
}
}
if(findup(new1)==findup(new4))
return 0;
if(findup(new2)==findup(new3))
return 0;
if(findup(new1)==findup(new2))
return 0;
if(findup(new3)==findup(new4))
return 0;
return 1;
}
int main()
{
freopen("AC.in","r",stdin);
freopen("AC.out","w",stdout);
scanf("%lf%lf%d",&lef,&rig,&n);
for(int i=1;i<=n;++i)
{
scanf("%lf%lf",&peo[i].x,&peo[i].y);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
if(i==j)
continue;
dist[i][j]=calc(i,j);
}
l=0,r=lef+rig;
while(r-l>0.0001)
{
double mid=(l+r)/2;
if(check(mid))
{
l=mid;
}
else
r=mid;
}
printf("%.2lf",l);
}