信息学奥赛一本通T1437：扩散

【题目描述】

一个点每过一个单位时间就会向四个方向扩散一个距离，如图。

两个点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

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair<int,int>
const double EPS = 1E-10;
const int MOD = 1E9+7;
const int N = 1000000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
struct Edge{
    int x,y;
    int dis;
    Edge(){}
    Edge(int x,int y,int dis):x(x),y(y),dis(dis){}
    bool operator < (const Edge &rhs)const{
        return dis<rhs.dis;
    }
}edge[N];
struct Node{
    int x,y;
    Node(){}
    Node(int x,int y):x(x),y(y){}
}node[N];
int tot;
int father[N];
int getDis(int i,int j){
    return abs(node[i].x-node[j].x)+abs(node[i].y-node[j].y);
}
int Find(int x){
    return father[x]==x?x:father[x]=Find(father[x]);
}
int Kruskal(int n){
    for(int i=1;i<=n;i++)
        father[i]=i;
    int num=0;
    int res=-INF;
    for(int i=1;i<=tot;i++){
        int x=edge[i].x;
        int y=edge[i].y;
        x=Find(x);
        y=Find(y);
        if(x!=y){
            res=max(res,edge[i].dis);
            num++;
            father[x]=y;
        }
        if(num==n)
            break;
    }
    return res;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&node[i].x,&node[i].y);

    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            edge[++tot].x=i;
            edge[tot].y=j;
            edge[tot].dis=getDis(i,j);
        }
    }

    sort(edge+1,edge+1+tot);
    int res=Kruskal(n);
    res=(res+1)/2;
    printf("%d\n",res);
    return 0;
}

信息学奥赛一本通T1437：二分与三分 扩散 归属于 二分与三分，更多同类题解源程序见：二分与三分 和 扩散