题解：AT_abc419_c [ABC419C] King's Summit

题意

在一张二维地图上，有 $n$ 个人，每秒可以向周围八个格子移动一格，问至少多少秒可以使全图的人在同一个点。

思路

首先，这一道题我们需要知道一个概念：切比雪夫距离。

切比雪夫距离

官方定义

在数学中，切比雪夫距离（Chebyshev distance）或是L∞度量，是向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差绝对值的最大值。以数学的观点来看，切比雪夫距离是由一致范数（uniform norm）（或称为上确界范数）所衍生的度量，也是超凸度量（injective metric space）的一种。
很好，是个人都看不懂。

我的解释

在一张八连通的二维地图上，从点 $(x1,y1)$ 到点 $(x2,y2)$ ， 他们之间的距离为 $\min(\operatorname{abs}(x1-x2),\operatorname{abs}(y1-y2))$ 。很好，就是这么简单。

---

然后我们经过计算可以知道 $x$ 或 $y$ 坐标相差最大的两个人移动到同一个点，只需要 $\dfrac{\operatorname{abs}(x_1-x_2+1)}{2}$ 或 $\dfrac{\operatorname{abs}(y_1-y_2)+1}{2}$ 秒。其中我们找的是最小值，选择最不利情况，所以最后的答案是 $\max(\frac{\operatorname{abs}(x_1-x_2+1)}{2},\frac{\operatorname{abs}(y_1-y_2+1)}{2})$ 。

AC Code

以下是本蒟蒻的代码。

#include<bits/stdc++.h>
using namespace std;
int n,maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;
int main(){
    cin>>n;
    while(n--){
        int x,y;
        cin>>x>>y;
        maxx=max(maxx,x);//求最小值和最大值。
        minx=min(minx,x);
        maxy=max(maxy,y);
        miny=min(miny,y);
    }
    cout<<max(abs(maxx-minx+1)/2,abs(maxy-miny+1)/2);//使用上面的公式。
    return 0;
}

AC记录。
管理大大求过