linkkkkk
题意：
给出一个n ∗ m的矩形，里面有k个点，从( 0 , 0 )走到( n , m )，使得过程中和这些点的最小距离最大，输出最大距离。
思路：
看到最小距离最大，首先想到二分。
比较思维的一个转化就是将运动轨迹看成是一个半径为m i d的圆，那么如果两个点之间的距离小于2 ∗ m i，这个圆就无法通过。
由于点的数量只有1000，所以直接暴力枚举两个点是否相交即可。注意也要判断是否超过边界。可以用并查集维护连通性。最后如果说上下、左右、上右、下左有联通的话，该值不可行。
代码：
// Problem: C. Safe Distance // Contest: Codeforces - 2020-2021 ICPC Southwestern European Regional Contest (SWERC 2020) // URL: https://codeforces.com/gym/103081/problem/C // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> //#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read(){ll 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 void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} const int maxn=2e5+100,inf=0x3f3f3f3f; const double eps=1e-6; int n,m,k; int nx[]={1,2,1,3}; int ny[]={3,4,2,4}; struct node{ double x,y; }pos[1100]; int root[maxn]; int Find(int x){ if(x!=root[x]) root[x]=Find(root[x]); return root[x]; } bool flag; bool check(double r){ rep(i,1,k+4) root[i]=i; for(int i=1;i<=k;i++){ if(pos[i].y+r>m){ int u=Find(i),v=Find(k+1); if(u!=v) root[u]=v; } if(pos[i].y<r){ int u=Find(i),v=Find(k+3); if(u!=v) root[u]=v; } if(pos[i].x<r){ int u=Find(i),v=Find(k+4); if(u!=v) root[u]=v; } if(pos[i].x+r>n){ int u=Find(i),v=Find(k+2); if(u!=v) root[u]=v; } for(int j=1;j<i;j++){ double tmp=(pos[i].x-pos[j].x)*(pos[i].x-pos[j].x)+(pos[i].y-pos[j].y)*(pos[i].y-pos[j].y); if(tmp<4*r*r){ int u=Find(i),v=Find(j); if(u!=v) root[u]=v; } } } if(Find(k+1)==Find(k+3)||Find(k+2)==Find(k+4)||Find(k+1)==Find(k+2)||Find(k+3)==Find(k+4)) return 0; return 1; } int main(){ n=read,m=read,k=read; rep(i,1,k) cin>>pos[i].x>>pos[i].y; double l=0,r=max(n,m); while(r-l>=eps){ double mid=(l+r)/2.0; if(check(mid)) l=mid; else r=mid; //cout<<l<<" "<<r<<endl; } printf("%.5f\n",l); return 0; }
