DDOSvoid's Blog

牛客 contest 166B 首都

发表于 更新于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

https://ac.nowcoder.com/acm/contest/166/B

简要题意：给定 $n$ 八连通二维平面上的点 $(x_i,y_i)$，求选择一个整点 $(x,y)$（可以不是给定点），使得所有给定点到它的距离和最小，求选择的方案数和最小的距离和

$n\le 10^5$

Solution

首先现将切比雪夫距离转成曼哈顿距离

然后我们取中位数，如果 $n$ 是奇数，那么中位数唯一

由于整数坐标的限制，我们不能直接除 $2$

这个时候我们要抖动一下防止变回去的时候出现小数

如果 $n$ 是偶数，那么我们就统计一下矩形中有多少点两维坐标的奇偶性相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100010
#define INF 100000000000000000ll
#define ll long long
using namespace std;

int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };

int n;

ll x[maxn], y[maxn];

ll D(ll x0, ll y0) {
    ll s = 0;
    for (int i = 1; i <= n; ++i)
        s += abs(x0 - x[i]) + abs(y0 - y[i]);
    return s / 2;
}

ll calc_even(ll l, ll r) {
    ll x = r - l + 1;
    if (l & 1 && r & 1) return x / 2;
    return x + 1 >> 1; 
}

ll calc_odd(ll l, ll r) {
    ll x = r - l + 1;
    if (l & 1 && r & 1) return x + 1 >> 1;
    return x / 2;
}

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

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x0, y0; cin >> x0 >> y0;
        x[i] = x0 + y0; y[i] = x0 - y0;
    }
    sort(x + 1, x + n + 1); sort(y + 1, y + n + 1);
    ll xl = x[n / 2], xr = x[n / 2 + 1], yl = y[n / 2], yr = y[n / 2 + 1];
    if (n & 1 || xl == xr && yl == yr) {
        ll sx = x[n + 1 >> 1], sy = y[n + 1 >> 1];
        if ((sx + sy) % 2 == 0) return cout << D(sx, sy) << "\n1\n", 0;
        ll ans = INF, Ans = 0;
        for (int i = 0; i < 4; ++i) {
            int tx = sx + dx[i], ty = sy + dy[i];
            if (D(tx, ty) < ans) ans = D(tx, ty), Ans = 1; 
            else if (D(tx, ty) == ans) ++Ans;
        }
        return cout << ans << "\n" << Ans << "\n", 0;
    }
    cout << D(xl, yl) << "\n";
    cout << calc_even(xl, xr) * calc_even(yl, yr) + calc_odd(xl, xr) * calc_odd(yl, yr) << "\n";
    return 0;
}