题解
- 如果,换个思路想想,我们把可以相通的点合并,那么最后只用判断能否有一条路经过
- 然后二分一个长度,以每个点为圆心画圆,将不能联通的放在同一个并查集内
- 那么如果左边的墙和下面的墙在同一个并查集内的话,那么就是不可能过去的嘛
- 还有就是上和下,下和右,上和左某一组在同一个并查集内的话,就无法从(0,0)到(x,y),感性理解一下
代码
1 #include <cstdio>
2 #include <iostream>
3 #include <cstring>
4 using namespace std;
5 const double eps=1e-4;
6 int n,fa[2010];
7 double l,r,ans,a[2010],b[2010],x,y;
8 int getfather(int x) { return !fa[x]?x:fa[x]=getfather(fa[x]); }
9 double sqr(double x) { return x*x; }
10 void merge(int x,int y)
11 {
12 int u=getfather(x),v=getfather(y);
13 if (u!=v) fa[u]=v;
14 }
15 bool check(double d)
16 {
17 memset(fa,0,sizeof(fa));
18 for (int i=1;i<=n;i++)
19 {
20 if (a[i]<=d) merge(i,n+1);
21 if (b[i]<=d) merge(i,n+2);
22 if (a[i]+d>=x) merge(i,n+3);
23 if (b[i]+d>=y) merge(i,n+4);
24 }
25 for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (sqr(a[i]-a[j])+sqr(b[i]-b[j])<=4*d*d) merge(i,j);
26 if (getfather(n+1)==getfather(n+2)) return false;if (getfather(n+1)==getfather(n+3)) return false;
27 if (getfather(n+2)==getfather(n+4)) return false;if (getfather(n+3)==getfather(n+4)) return false;
28 return true;
29 }
30 int main()
31 {
32 freopen("AC.in","r",stdin),freopen("AC.out","w",stdout);
33 scanf("%lf%lf%d",&x,&y,&n);
34 for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i],&b[i]);
35 l=0,r=1e6;
36 while (r-l>=eps)
37 {
38 double mid=(l+r)/2;
39 if (check(mid)) ans=mid,l=mid+eps; else r=mid;
40 }
41 printf("%.2lf",ans);
42 }