一本通题解——1437：扩散

题目链接

一本通OJ：http://ybt.ssoier.cn:8088/problem_show.php?pid=1437。

我的OJ：http://47.110.135.197/problem.php?id=4462。

题目

题目描述

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

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

分析

数学相关

直线距离

A 点坐标为（x1, y1），B 点坐标为（x2, y2），那么 AB 之间的距离为  。

曼哈顿距离

A 点坐标为（x1, y1），B 点坐标为（x2, y2），那么 AB 之间的曼哈顿距离为 。

两个距离的关系

上图中红线代表曼哈顿距离，绿色代表欧氏距离，也就是直线距离，而蓝色和黄色代表等价的曼哈顿距离。

题目分析

根据题意，个点每过一个单位时间就会向四个方向扩散一个距离。我们使用输入样例来分析输出结果。开始我们有两个点 （0, 0）和（5, 5）。时间和扩散点坐标如下表。

时间	A 点				B 点
t=0	（0, 0）				（5, 5）
	上	左	下	右	上	左	下	右
t=1	（0, 1）	（1, 0）	（0, -1）	（-1, 0）	（5, 6）	（6, 5）	（5, 4）	（4, 5）
t=2	（0, 2）	（2, 0）	（0, -2）	（-2, 0）	（5, 7）	（7, 5）	（5, 3）	（3, 5）
t=3	（0, 3）	（3, 0）	（0, -3）	（-3, 0）	（5, 8）	（8, 5）	（5, 2）	（2, 5）
t=4	（0, 4）	（4, 0）	（0, -4）	（-4, 0）	（5, 9）	（9, 5）	（5, 1）	（1, 5）
t=5	（0, 5）	（5, 0）	（0, -5）	（-5, 0）	（5, 10）	（10, 5）	（5, 0）	（0, 5）
......

下面我们绘制一下当 t=5 的时候情况，如下图所示，黑色为 （0, 0）点扩散情况，红色为（5, 5）点扩散情况。可以非常清楚的看到当 t=5 的时候，发生了连通性。

连通性判断

我们借用网络上的一个图片来说明连通性。假设第一个点 A，该点的坐标为（1, -4）。那么在 t=0 的时刻，该点的位置如下图所示。

然后 A 点开始向四个方向扩散，扩散后变成 4 个点，对应的时间和坐标关系如下表。

时间	上点	右点	下点	左点
t = 1	（1, -3）	（2, -4）	（1, -5）	（0, -4）
t = 2	（1, -2）	（3, -4）	（1, -6）	（-1, -4）
......
t = 6	（1, 2）	（7, -4）	（1, -10）	（-5, -4）

当 t=6 的时候，扩散以后的图形如下图所示。

将扩散后的 4 个点用直线连接，可以看出，扩散的边界刚好是过菱形顶点的一次函数。那么我们可以推导出下表所示的时间函数。

点坐标	时间函数
（Ax, Ay）	y = -x + a1 + b1 + t
（Ax, A-y）	y = x - a1 + b1 - t
（A-x, Ay）	y = x - a1 + b1 + t
（A-x, A-y）	y = -x + a1 + b1 - t

现在我们加上另外一个点 B（a2, b2），开始的坐标为 （5, 3），经过 t=6 秒后，A 点和 B 点的图形如下图所示。

从上图我们可以清晰的看到，当两点的边界重合之后，这两点便直接连通了。于是通过解对应方程，我们可以得到两点边界重合的时间如下表所示。

A 点和 B 点相对位置	象限	重合时间
(a1 > b1 && a2 > b2) || (a1 < b1 && a2 < b2)	第一、第三象限	abs(a1 + b1 - a2 - b2)/2
(a1 > b1 && a2 < b2) || (a1 < b1 && a2 < b2)	第二、第四象限	abs(a1 - b1 - a2 + b2)/2

算法思路

经过上面分析，我们知道可以使用查并集知识点来解决。这里我们用二分查找。

首先，这些点呈菱形扩散，那么如果两点在 t 个单位时间能相遇，那么两点的曼哈顿距离 < 2*t。

P.S.

使用曼哈顿距离而不使用直线距离，主要是为了降低计算量。

二分查找

1、前提：从连通性角度来说，假设 t 秒区域连通。那么超过 t 秒时，区域肯定也是连通的。

2、二分查找的左边界为 0，右边界选择为 1e9（X[i]、Y[i] 的最大值）。

3、每次取中间点 mid 后，从任意一个点出发尝试遍历所有点。a 能达到 b 的条件一定是 a 到 b 的曼哈顿距离不超过 2 倍的 mid 值。如果能成功遍历所有点，说明当前 mid 符合条件；反之，则不符合条件。

4、符合条件，右边界移动，我们尝试更小 mid 的可能性。如果不符合条件，左边界移动，我们尝试更大 mid 的可能性。

5、一直到不符合二分查找条件，即 left ≤ right，不成立。right 就是我们需要的答案。

AC参考代码

#include <bits/stdc++.h>
using namespace std;

typedef struct stCoord{
    int x;//x坐标
    int y;//y坐标
} COORD;

const int MAXN = 50+2;
COORD data[MAXN];//原始坐标
int dis[MAXN][MAXN];//距离
int spread[MAXN];//上一次扩散位置

bool check(int x, int n) {
    //根据扩散时间x，遍历所有点，查找是否存在连通
    bool vis[MAXN] = {};//是否已经访问
    int step=0;
    int time=1;

    spread[1] = 1;
    vis[1] = true;
    while (step^time) {
        step++;
        for (int i=1; i<=n; i++) {
            if (true==vis[i]) {
                //已经访问，则跳过
                continue;
            }

            if (dis[spread[step]][i] <= x*2) {
                vis[i] = true;
                spread[++time] = i;
            }
        }
    }

    return time==n;
}

int main() {
    int n;
    cin>>n;

    int i, j;
    for (i=1; i<=n; i++) {
        cin >> data[i].x >> data[i].y;
    }

    //预处理，计算距离
    for (i=1; i<n; i++) {
        for (j=i+1; j<=n; j++) {
            dis[i][j] = dis[j][i] = abs(data[i].x-data[j].x)+abs(data[i].y-data[j].y);
        }
    }

    int left=0;
    int right=1e9;
    int mid;
    while (left<=right) {
        mid = left+((right-left)>>1);

        //按照mid为扩散时间，检查是否存在连通
        if (true==check(mid, n)) {
            //已经有连通，缩小
            right = mid-1;
        } else {
            //没有连通，扩大
            left = mid+1;
        }
    }

    cout << left << endl;

    return 0;
}