题解：P13080 [NOISG 2017] Best Places / 最佳选址

_fallen_leaves_ · 2025-07-05 19:07:14 · 题解

P13080 [NOISG 2017] Best Places / 最佳选址

题意

给出 n 个人的坐标，记作标为 (X_i,Y_i) ，选择一个点，记坐标为 (X,Y)，使所有人的 |X-X_i|+|Y-Y_i| 和最小。

思路

分别考虑 x 轴与 y 轴，我们分别把 x 轴与 y 轴从小到大排序，取 x 轴与 y 轴最中间的数，也就是我们的答案，这样可以使所有人的路程和最短。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000005],b[1000005],s,s2;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    cout<<a[n/2+1]<<" "<<b[n/2+1];
    return 0;
}