最小化曼哈顿距离(二维例子)

最小化曼哈顿距离(二维)

https://codeforces.com/contest/1486/problem/B

题意:给出二维平面上 \(n\) 个点的坐标 \((x_i, y_i)\),求有多少个点,能使 \(n\) 个点到其的距离总和最小(目标点可以和给出的点重合)。

题解:试想一维的情况,在一条直线上有 \(n\) 个点,找出一个点使所有点到它的距离之和最小,这个点肯定是中位数!!!同理。。。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const char nl = '\n';
const int N = 1000 + 50;

int x[N], y[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt;
    for (cin >> tt; tt; tt--){
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i];
        sort(x + 1, x + n + 1);
        sort(y + 1, y + n + 1);
        LL ans = 1;
        if (n % 2 == 0) ans = (LL)(x[n / 2 + 1] - x[n / 2] + 1) * (y[n / 2 + 1] - y[n / 2] + 1);
        cout << ans << nl;
    }

    return 0;
}

上一篇:修建草坪


下一篇:[正睿集训2021] 字符串