CF491B New York Hotel 题解

题意：

New York 是个由 $N$ 条垂直道路 (编号为 $1\sim N$) 和 $M$ 条水平道路 (编号为 $1\sim M$ ) 组成的城市。

$C$ 个朋友分别住在该城市中的 $C$ 个酒店中，这些酒店分别坐落在垂直道路和水平道路的相交处。由于他们要庆祝 cxy 的生日，于是他们想去 $H$ 个餐馆中的一个 (当然，这 $H$ 个餐厅也坐落在垂直道路和水平道路的相交处)。

他们想知道，这 $C$ 个酒店到餐馆的最大距离 (即最远的酒店到餐厅的距离) 的最小可能值是多少。帮助朋友们确定一个合适的餐厅以庆祝生日。

假设相邻两个相交处的距离均等于 $1$。

输入格式：

第一行包含两个正整数 $N,M ~(N,M\le 10^9)$ ，描述城市的大小。

第二行包含一个正整数 $C~ (C\le 10^5)$，表示朋友们住的酒店个数。

接下来的 $C$ 行，每行两个正整数 $x,y ~(x\le N,y\le M)$ ，描述第 $i$ 个酒店的坐标。

紧跟着一行，包含一个正整数 $H~ (H\le 10^5)$ ，表示餐馆的个数。

接下来的 $H$ 行，每行两个正整数 $x,y$ ，以类似地格式给出餐馆的坐标。

注意有些餐馆和酒店的坐标可能相同。

输出格式：

第一行输出一个整数，表示距离的最大距离的最小可能值。

第二行输出一个整数，表示达到这个最优值的餐馆的编号。如果有多个餐馆均符合要求，输出任意一个均可。

我们只需要知道每个餐馆对应的最远酒店在哪里就好了

回忆~~小学数学~~，点到点集的最远距离怎么算的？

答案就是找点集的外接圆，然后枚举在外接圆上的点找最大的。

考虑曼哈顿距离的计算

$d(i,j)=|x_i-x_j|+|y_i-y_j|$

那么这个点一定在Manhattan平面上所有人的“外接圆”上

这个Manhattan平面的外接圆长啥样呢，我搬了张图

下图是 Manhattan 平面上半径为 $1$ 的圆

考虑怎么求这个外接圆

观察公式 $|x_i-x_j|+|y_i-y_j|$ 可以发现，一共有 $4$ 种情况

$(x_i-x_j)-(y_i-y_j)\\ (x_j-x_i)-(y_i-y_j)\\ (x_i-x_j)-(y_j-y_i)\\ (x_j-x_i)-(y_j-y_i)$

这么看好像有点花，我们用 $a,b,c,d$ 来替代 $x_i,y_i,x_j,y_j$

$\begin{aligned} (a-c)-(b-d) &\Rightarrow (a-b)-(c-d)\\ (c-a)-(b-d) &\Rightarrow (-a-b)-(-c-d)\\ (a-c)-(d-b) &\Rightarrow (a+b)-(c+d)\\ (c-a)-(d-b) &\Rightarrow (-a+b)-(-c+d) \end{aligned}$

而在枚举每个餐厅的时候，其实就相当于固定了 $c,d$ 。

于是我们只要统计每个人的 $a-b,-a-b,a+b,-a+b$ 各自的最大值，这样减掉后面的 $c,d$ 就是极大值了。

时间复杂度 $\mathcal{O}(4c+h)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)())

int n,m,c,h,p,s1,s2,s3,s4,res=INF;
void up(int &x,int y) {x < y ? x=y : 0;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> c; s1=s2=s3=s4=-INF;
    for(int i=1,x,y; i<=c; i++)
    {
        cin >> x >> y;
        up(s1,x+y); up(s2,x-y); up(s3,-x+y); up(s4,-x-y);
    }
    cin >> h;
    for(int i=1,x,y,t; i<=h; i++)
    {
        cin >> x >> y;
        t=max({s1-(x+y), s2-(x-y), s3-(-x+y), s4-(-x-y)});
        res > t ? res=t,p=i : 0;
    }
    cout << res << '\n' << p << '\n';
    return 0;
}