DDOSvoid's Blog

校内赛 T2 辣辣快递 max pro plus ultra ++

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

题目描述

简要题意：给定 $n$ 个点和 $m$ 个特殊位置，两点之间的距离为曼哈顿距离

要求新建一个特殊位置，使得所有点到最近的特殊位置的最大值最小

$n,m\le 10^5$

Solution

首先用树状数组在四个方向上计算出每个点距离最近的特殊位置

然后二分答案，判断的时候将图转为八连通，这样利用切比雪夫距离可以将两个维度分开来判断

更进一步，我们令 $mxx$ 为所有点的横坐标的最大值，$mnx$ 为所有点的横坐标的最小值，$mxy$ 和 $mny$ 同理

则我们应该选 $(\frac{mnx+mxx}{2},\frac{mny+mxy}{2})$，问题就是我们要确定在整数坐标的情况下是否能变回去

我们不能只在四连通的方向上抖动，而应该在下取整之后在 $[-1,2]$ 的范围抖动

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
#include <set>
#define maxn 100010
#define maxm 100010
#define ll long long
#define gc getchar
#define ci const int
#define pb push_back
#define lowbit(i) ((i) & (-i))
#define INF 2000000000000ll
#define cn const node
using namespace std;

int read() {
    int x = 0, f = 0; char c = gc();
    while (!isdigit(c)) f |= c == '-', c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return f ? -x : x;
}

inline ll max(ll a, ll b, ll c, ll d) { return max(max(a, b), max(c, d)); } 

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

int n, m;

ll ans[maxn];

struct node {
    ll x, y, id;

    friend bool operator < (cn &u, cn &v) { return u.x < v.x; } 
} a[maxn], b[maxn];

ll c[maxn * 4], N, cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) 
        c[i] = a[i].y, c[i + n] = a[i].x;
    for (int i = 1; i <= m; ++i)
        c[i + 2 * n] = b[i].x, c[i + 2 * n + m] = b[i].y;
    sort(c + 1, c + 2 * n + 2 * m + 1); cnt = unique(c + 1, c + 2 * n + 2 * m + 1) - c - 1;
    for (int i = 1; i <= n; ++i) {
        a[i].x = lower_bound(c + 1, c + cnt + 1, a[i].x) - c;
        a[i].y = lower_bound(c + 1, c + cnt + 1, a[i].y) - c;
    }
    for (int i = 1; i <= m; ++i) {
        b[i].x = lower_bound(c + 1, c + cnt + 1, b[i].x) - c;
        b[i].y = lower_bound(c + 1, c + cnt + 1, b[i].y) - c;
    }
}

ll B1[4 * maxn], B2[4 * maxn];
void add(int i, ll v) {
    while (i <= cnt) B1[i] = min(B1[i], v), i += lowbit(i);
}

void Add(int i, ll v) { while (i) B2[i] = min(B2[i], v), i -= lowbit(i); } 

ll query(int i) {
    ll s = INF;
    while (i) s = min(s, B1[i]), i -= lowbit(i);
    return s;
}

ll Query(int i) {
    ll s = INF;
    while (i <= cnt) s = min(s, B2[i]), i += lowbit(i);
    return s;
}

bool check(ll p) {
    ll mxx = -INF, mxy = -INF, mnx = INF, mny = INF, sum = 0;
    for (int i = 1; i <= n; ++i) {
        ll id = a[i].id, x = a[i].x, y = a[i].y;
        if (ans[id] <= p) continue; ++sum;
        mxx = max(mxx, x); mxy = max(mxy, y);
        mnx = min(mnx, x); mny = min(mny, y);
    }
    if (!sum) return 1;
    ll X = mxx + mnx >> 1, Y = mxy + mny >> 1;
    for (int x = X - 1; x <= X + 2; ++x)
        for (int y = Y - 1; y <= Y + 2; ++y)
            if ((x + y) % 2 == 0 && max(mxx - x, x - mnx, mxy - y, y - mny) <= p) return 1; 
    return 0;
}

int main() {
    while (cin >> n >> m) { 
        for (int i = 1; i <= n; ++i) a[i].x = read(), a[i].y = read(), a[i].id = i; 
        for (int i = 1; i <= m; ++i) b[i].x = read(), b[i].y = read();
        init_hash(); fill(ans, ans + maxn, INF);

        int j = 0; sort(a + 1, a + n + 1); sort(b + 1, b + m + 1); fill(B1, B1 + 4 * maxn, INF);
        for (int i = 1; i <= n; ++i) { 
            while (j < m && b[j + 1].x <= a[i].x) ++j, add(b[j].y, -c[b[j].x] - c[b[j].y]);
            ans[a[i].id] = min(ans[a[i].id], c[a[i].x] + c[a[i].y] + query(a[i].y));
        }
        j = m + 1; fill(B1, B1 + 4 * maxn, INF);
        for (int i = n; i; --i) { 
            while (j > 1 && b[j - 1].x >= a[i].x) --j, add(b[j].y, c[b[j].x] - c[b[j].y]);
            ans[a[i].id] = min(ans[a[i].id], -c[a[i].x] + c[a[i].y] + query(a[i].y));
        }

        j = m + 1; fill(B2, B2 + 4 * maxn, INF);
        for (int i = n; i; --i) { 
            while (j > 1 && b[j - 1].x >= a[i].x) --j, Add(b[j].y, c[b[j].x] + c[b[j].y]);
            ll v1 = Query(a[i].y), v2 = -c[a[i].x] - c[a[i].y];
            ans[a[i].id] = min(ans[a[i].id], -c[a[i].x] - c[a[i].y] + Query(a[i].y));
        }
    
        j = 0; fill(B2, B2 + 4 * maxn, INF); 
        for (int i = 1; i <= n; ++i) { 
            while (j < m && b[j + 1].x <= a[i].x) ++j, Add(b[j].y, -c[b[j].x] + c[b[j].y]);
            ans[a[i].id] = min(ans[a[i].id], c[a[i].x] - c[a[i].y] + Query(a[i].y));
        }

        for (int i = 1; i <= n; ++i) {
            ll x = c[a[i].x], y = c[a[i].y];
            a[i].x = x + y; a[i].y = x - y; 
        }
        ll l = 0, r = INF, mid, ans;
        while (l <= r) {
            mid = l + r >> 1;
            if (check(mid)) ans = mid, r = mid - 1;
            else l = mid + 1;
        } cout << ans << "\n";
    }
    return 0;
}