cf491b.md

提示 1： 两点的曼哈顿距离（就是题中要求的东西）为 $|x_1-x_2|+|y_1-y_2|$ ，而我们要对其取最大值。这个东西如何比较？

提示 2： 最大值满足性质 $\max(\max(a,b),c)=\max(a,b,c)$ ，如果我们能将绝对值表示为最大值形式，可以直接独立考虑每一项成分。

直觉上来看，一个点确定，另一个与其曼哈顿距离一定的点构成一个菱形，且菱形的四条边的斜率为 $1$ 或 $-1$ 。

因此我们可能考虑的是 过某一点作斜率为 $1$ 或 $-1$ 的线与已有直线之间的最大距离。

事实上，我们求的就是该数值的最大值。接下来用数学详细说明这一点。

我们假设房子构成集合 $A$ ，目的地构成集合 $B$ ，则我们要求的是一个目的地，使得所有房子到目的地的距离的最大值最小，用数学符号可以表达如下——

$$\min\limits_{(x,y)∈ B}\max_{(x',y')∈ A}|x-x'|+|y-y'|$$

但是单一的绝对值有多种情况，不容易考虑，因此，考虑到提示 2，我们尝试将绝对值替换为一堆数的最大值。

而事实上：

$|x-x'|+|y-y'|=\max(x-x',x'-x)+\max(y-y',y'-y)$

$=\max(x-x'+y-y',x-x'+y'-y,x'-x+y-y',x'-x+y'-y)$

$=\max((x+y)-(x'+y'),(x-y)-(x'-y'),(x'-y')-(x-y),(x'+y')-(x+y))$

于是，（注意下面的式子中 $(x,y)$ 固定）

$\max_{(x',y')∈ A}|x-x'|+|y-y'|$

$=\max_{(x',y')∈ A}\max((x+y)-(x'+y'),(x-y)-(x'-y'),(x'-y')-(x-y),(x'+y')-(x+y))$

$=\max(\max_{(x',y')∈ A}[(x+y)-(x'+y')],\max_{(x',y')∈ A}[(x-y)-(x'-y')],\max_{(x',y')∈ A}[(x'-y')-(x-y)],\max_{(x',y')∈ A}[(x'+y')-(x+y))]$

$=\max[(x+y)-\min_{(x',y')∈ A}(x'+y'),(x-y)-\min_{(x',y')∈ A}(x'-y'),\max_{(x',y')∈ A}(x'-y')-(x-y),\max_{(x',y')∈ A}(x'+y')-(x+y)]$

而这里 $\max_{(x',y')∈ A}(x'+y'), \min_{(x',y')∈ A}(x'+y'), \max_{(x',y')∈ A}(x'-y'), \min_{(x',y')∈ A}(x'-y')$ 可以预处理得到，因此对于每一组 $(x,y)$ 可以 $\mathcal{O}(1)$ 计算数值，因此我们完成本题。

时间复杂度为 $\mathcal{O}(C+H)$ .

具体代码如下（只包含中间处理部分）——

def main():
    I()
    n = II()
    mi_x, ma_x = inf, -inf
    mi_y, ma_y = inf, -inf
    for _ in range(n):
        x, y = MII()
        mi_x = min(mi_x, x + y)
        ma_x = max(ma_x, x + y)
        mi_y = min(mi_y, x - y)
        ma_y = max(ma_y, x - y)
    
    m = II()
    ans = inf
    idx = 0
    for i in range(1, m + 1):
        x, y = MII()
        d = max(x + y - mi_x, ma_x - x - y,
                x - y - mi_y, ma_y - x + y)
        if d < ans:
            ans = d
            idx = i
    
    print(ans)
    print(idx)