目录
思路【floyd+dp】：
【代码实现：floyd+dp】
思路2:并查集+二分
【代码实现：并查集+二分】
最后来个小小的总结：
【题目描述】
一个点每过一个单位时间就会向 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≤Xi,Yi≤50；
对于 100% 的数据，满足 1≤n≤50,1≤Xi,Yi≤10^9。
设两个点A、B以及坐标分别为
，则A和B两点之间的距离为：
以上的式子在代码中不好表示，那就根据数学稍微改变一下：
这样一来我们可以十分方便的把这个式子带入到代码当中（绝对值的表示为
，记得在前面加头文件
#include<cmath>
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++) if(i!=k)
for(int j=1;j<=n;j++) if(j!=i && j!=k)
floyd[i][j]=min(floyd[i][j],floyd[i][k]+floyd[j][k]);/*
解释一下定义：他是要存在了公共区域才算OK啊
是全部都有公共区域
而且要求最小的时刻，那就意味着我们要让所有点之间的距离尽可能的小
在这个方面的基础上，最有效的办法就是就是求任意两点直接最短路的算法
dijkstra算法 / spfa算法 / floyd算法 都是有效的最短路算法
*/
#include<cmath>
#include<cstdio>
#include<cstdio>
#include<algorithm>
using namespace std;
int x[55],y[55];
int w[55][55];//记录的是两个点之间的距离
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
w[i][j]=w[j][i]=abs(x[i]-x[j])+abs(y[i]-y[j]);//求出两点的距离
//距离公式是abs(x0 - x1) + abs(y0 +y1)，
//经过多次画图之后知道，其实每一次的扩展就是在外面多一圈
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
w[i][j]=min(w[i][j],max(w[i][k],w[k][j]));
/*
寻找最短距离
仔细一看有点像floyd算法，求任意两点最短路的算法
floyd的精髓所在就是我们用三个循环，然后就可以判断出
他到底是直接到距离最短，还是经过其他点相加的路程距离最短
所以这一步是不可以没有的，我们最先找到的距离公式只是片面的
floyd才是最根本的一个距离的记录，我也发现把这一部分删掉就会wa掉
*/
int ans=0;//记录最小的时刻
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
ans=max(ans,w[i][j]);//ans就是更大的距离
printf("%d\n",(ans+1)/2);
/*
两个点连通仅当距离<=时间*2 这是推理的一条公式
然后根据这条公式我们可以知道，w[i][j]记录的就是距离
而ans是最大距离的记录成立的跑过floyd之后最短的最大距离
（之所以要找到最大是因为我们要让所有都连通，那就要兼顾最坏的情况）
所以的话，我们的ans要小于等于时间乘以2
那么知道距离，时间就是除以2
然后这个+1是为了防止出错，怎么个出错法呢？
就是那些交叉的，其实差一点点才能够联通
但是按照我们的算法电脑默认连通其实只是衔接上没有算得上是连通
这是时候就要加多一步来实现
（最主要的是双数的时候没有影响，只是影响单数的衔接情况）
*/
return 0;
}
//https://blog.csdn.net/xianpingping/article/details/79947091
//优秀的floyd算法的解释博客 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int x,y;
}a[55];
int n,d[55][55],fa[55];//d[i][j]记录距离，fa记录父亲
inline int abs(int x){return x>0?x:-x;}
int juli(node n1,node n2){return abs(n1.x-n2.x)+abs(n1.y-n2.y);}
int find(int x)
{
if(x==fa[x])return x;
else return fa[x]=find(fa[x]);
}
bool check(int x)
{
for(int i=1;i<=n;i++)fa[i]=i;//先规定好每个点的父亲节点
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(d[i][j]<=x*2)//同样的距离小于两倍的时间
{
int fx=find(i),fy=find(j);
//先找到自己共同的祖先，就是要相交的时候到达的点
if(fx!=fy)fa[fx]=fy;
//如果不一样的话，将其中一个与另一个变为一样的
}
int sum=0;
for(int i=1;i<=n;i++)
{
if(fa[i]==i)sum++;//祖先相同的话，这样的走向就成立
if(sum==2)return false;
/*如果有两个祖先的话，说明最短距离没有找对，
因为只能允许一个最近的祖先*/
}
return true;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
d[i][j]=d[j][i]=juli(a[i],a[j]);
int l=0,r=999999999,ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)==true){r=mid-1;ans=mid;}
//目的求最小，正确往左移
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}可以求距离的算法（或者说和距离有关系的）
spfa算法（bfs）
dijkstra算法（单源最短路径算法）
floyd算法（任意点之间的最短路）
并查集（找到一个共同目标为父亲节点）
目前我找到的最有效最好用的就是这四个了