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;
}