Luogu P3964 [TJOI2013]松鼠聚会

题目描述

https://www.luogu.com.cn/problem/P3964

简要题意：给定 $n$ 个八连通二维平面上的点 $(x_i,y_i)$，求选一个给定点 $(x_i,y_i)$ 作为集合点，使得其它所有给定点到它的距离和最小

$n\le 10^5$

Solution

切比雪夫距离计算距离和很不方便，我们转换成曼哈顿距离将两维分开

最后将答案除 $2$ 即可，注意到答案一定是偶数

#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100010
#define cn const node
#define ll long long
#define INF 1000000000000000000ll
using namespace std;

int n;

struct node {
    int x, y, idx, idy;
} a[maxn];

ll sx[maxn], sy[maxn];

ll ans = INF;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x, y; cin >> x >> y;
        a[i].x = x + y; a[i].y = x - y;
    }
    sort(a + 1, a + n + 1, [](cn &u, cn &v) { return u.x < v.x; });
    for (int i = 1; i <= n; ++i) {
        sx[i] = sx[i - 1] + a[i].x;
        a[i].idx = i; 
    }
    sort(a + 1, a + n + 1, [](cn &u, cn &v) { return u.y < v.y; });
    for (int i = 1; i <= n; ++i) { 
        sy[i] = sy[i - 1] + a[i].y;
        a[i].idy = i;
    }
    for (int i = 1; i <= n; ++i) {
        int idx = a[i].idx, idy = a[i].idy, x = a[i].x, y = a[i].y;
        ll v = 1ll * x * idx - sx[idx] + (sx[n] - sx[idx]) - 1ll * x * (n - idx);
        v += 1ll * y * idy - sy[idy] + (sy[n] - sy[idy]) - 1ll * y * (n - idy);
        ans = min(ans, v); 
    } cout << ans / 2 << endl;
    return 0;
}