试题描述
|
一个点每过一个单位时间就会向 4 个方向扩散一个距离,如图所示:两个点 a 、b 连通,记作 e(a,b),当且仅当 a 、b 的扩散区域有公共部分。连通块的定义是块内的任意两个点 u、v 都必定存在路径e(u,a0),e(a0,a1),…e(ak,v)。
给定平面上的n个点,问最早什么时候它们形成一个连通块。 |
输入
|
第一行一个数 n ,以下 n 行,每行一个点坐标。
|
输出
|
输出仅一个数,表示所有点形成连通块的最早时刻。
|
输入示例
|
2
0 0 5 5 |
输出示例
|
5
|
其他说明
|
数据范围与提示
对于 20%的数据,满足 1≤n≤5,1≤X[i],Y[i]≤50; 对于 100% 的数据,满足 1≤n≤50,1≤X[i],Y[i]≤10^9。 |
弱智的二分答案,并查集维护是否联通
然后就没了,一直每条对是因为二分边界小了QAQ
下面给出代码:
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<cmath> using namespace std; inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } int n; struct node{ int a,b; }s[1006]; int f[1006]; bool c(int x,int y,int z){return ((abs(s[x].a-s[y].a)+abs(s[x].b-s[y].b))<=z);} int getf(int v){return v==f[v]?f[v]:f[v]=getf(f[v]);} int check(int x){ int cnt=0; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(c(i,j,x*2)) f[getf(j)]=getf(i); for(int i=1;i<=n;i++) if(f[i]==i) cnt++; return (cnt==1); } int main(){ n=rd(); for(int i=1;i<=n;i++){ s[i].a=rd(); s[i].b=rd(); } int ans=0; int l=0,r=1e8*2; while(l<=r){ int mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } printf("%d",ans); return 0; }