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

· · 题解

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

传送门

思路：

对于一维数轴上的坐标，使所有点到该点的距离之和最小的点是该点集的中位数。因此，最优 X 坐标是所有选手 X_i 的中位数，最优 Y 坐标是所有选手 Y_i 的中位数。

求中位数时，排序，再取中间数即可。

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int x[N],y[N],n;
int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    sort(x+1,x+1+n);//排序求中位数
    sort(y+1,y+1+n);
    cout<<x[n/2+1]<<" "<<y[n/2+1];//下标从一开始，所以要+1
    return 0;
}