ABC419 C

_std_O2 · 2025-08-17 15:41:55 · 题解

简要题意

在一个平面中给你 n 个点每个点的坐标是 (R_i,C_i) 你需要在平面内找到一个点，使这个点到所有点的切比雪夫距离的最大值最小，请求出这个值。

两点之间的切比雪夫距离定义为 \max(|x_a-x_b|,|y_a-y_b|)。

分析

我们可以首先考虑一维的问题：在线段上给定 n 个点，在线段上找一个点，使得这 n 个点到这个点的距离最大值最小。

显然，这个点应在这给定的最左边那个点和最右边那个点的中点（初一知识）。

那我们就可以推广到二维的情况了，将两个维度拆开，则这时使这个点到所有点的切比雪夫距离的最大值最小的那个点的坐标就是 (\frac{R_{min}+R_{max}}{2},\frac{C_{min}+C_{max}}{2})。

Code

#include <iostream>
using namespace std;
int R[200005],C[200005];
int N;
int main() {
    cin>>N;
    for (int i=1;i<=N;++i) {
        cin >> R[i] >> C[i];
    }
    sort(R+1,R+N+1);
    sort(C+1,C+N+1);
    int x_p=(R[1]+R[N])/2;
    int x_dis=max(R[1]-x_p,R[N]-x_p);
    int y_p=(C[1]+C[N])/2;
    int y_dis=max(C[1]-y_p,C[N]-y_p);
    cout<<max(x_dis,y_dis);
    return 0;
}