洛谷P2218《[HAOI2007]覆盖问题》

七月 30, 2019 3695

题目描述

某人在山上种了N棵小树苗。冬天来了，温度急速下降，小树苗脆弱得不堪一击，于是树主人想用一些塑料薄膜把这些小树遮盖起来，经过一番长久的思考，他决定 用3个L*L的正方形塑料薄膜将小树遮起来。

我们不妨将山建立一个平面直角坐标系，设第i棵小树的坐标为（Xi,Yi），3个L*L的正方形的边要求平行 与坐标轴，一个点如果在正方形的边界上，也算作被覆盖。当然，我们希望塑料薄膜面积越小越好，即求L最小值。

输入格式

第一行有一个正整数N，表示有多少棵树。

接下来有N行，第i+1行有2个整数Xi,Yi，表示第i棵树的坐标，保证不会有2个树的坐标相同。

输出格式

一行，输出最小的L值。

输入输出样例

输入 #1

1
2
3
4
5
4
0 1
0 -1
1 0
-1 0

输出 #1

1
1

说明/提示

数据范围

100%的数据，-1,000,000,000<=Xi,Yi<=1,000,000,000

30%的数据，N<=100

50%的数据，N<=2000

100%的数据，N<=20000

解析

显然答案具有单调性，因为边长为 k 的正方形能覆盖的话，边长为 k + 1 的正方形一定能覆盖
考虑二分答案

首先用一个最小的矩形覆盖所有的点

很容易想到一个做法：先把矩形的左上角、右下角用正方形覆盖，再把中间的用正方形覆盖
然而这样是不行的，反例很多，这里就不写了
但是换个思路，矩形的四个角一定会有贴着边放的正方形

所以换一个做法：枚举矩形的四个角，放正方形；此时还剩下一些点，再找一个最小的矩形覆盖所有点，递归进去做即可，深度只有 3 层

代码实现

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
//
//  LuoguP2218.cpp
//  Title: [HAOI2007]覆盖问题
//  Alternatives: BZOJ1052
//  Debugging
//
//  Created by HandwerSTD on 2019/7/25.
//  Copyright © 2019 HandwerSTD. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;
using std::min;
using std::max;

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }

const int MAXN = 20000 + 10;
const int INF = 0x3f3f3f3f;

lli n, maxx = -(0x3f3f3f3f), minx = (0x3f3f3f3f), maxy = -(0x3f3f3f3f), miny = (0x3f3f3f3f);
lli x[MAXN], y[MAXN];
int cov[MAXN];

/**
 *
 * 确定一个最小的矩形使得这个矩形可以覆盖所有点。
 * 枚举这个矩形的四个角，把一个正方形放到这个角上，
 * 有一些点会被覆盖，此时递归进去确定剩下未被覆盖的点即可
 *
 */

inline void _Cover(int lx, int rx, int ly, int ry, int ts) {
    for (int i = 1; i <= n; ++i)
        if (!cov[i]
            && lx <= x[i] && x[i] <= rx
            && ly <= y[i] && y[i] <= ry)
            cov[i] = ts;
}

inline void Uncover(int ts) {
    for (int i = 1; i <= n; ++i)
        if (cov[i] == ts)
            cov[i] = 0;
}

inline int _CHECK(int mid, int depth) {
    lli minx = INF, maxx = -INF, miny = INF, maxy = -INF;
    for (int i = 1; i <= n; ++i)
        if (!cov[i]) {
            minx = min(minx, x[i]); maxx = max(maxx, x[i]);
            miny = min(miny, y[i]); maxy = max(maxy, y[i]);
        }
    if (max(maxx - minx, maxy - miny) <= mid) return 1;
    if (depth == 3) return 0;
    _Cover(minx, minx + mid, miny, miny + mid, depth); // ld
    if (_CHECK(mid, depth + 1))
        return 1;
    Uncover(depth);
    _Cover(minx, minx + mid, maxy - mid, maxy, depth); // lu
    if (_CHECK(mid, depth + 1))
        return 1;
    Uncover(depth);
    _Cover(maxx - mid, maxx, miny, miny + mid, depth); // rd
    if (_CHECK(mid, depth + 1))
        return 1;
    Uncover(depth);
    _Cover(maxx - mid, maxx, maxy - mid, maxy, depth); // ru
    if (_CHECK(mid, depth + 1))
        return 1;
    Uncover(depth);
    return 0;
}

bool Check(int mid) {
    memset(cov, 0, sizeof cov);
    return _CHECK(mid, 1);
}

int main() {
    n = getint();
    for (int i = 1; i <= n; ++i) { x[i] = getint(); y[i] = getint(); }
    int l = 0, r = 2e9;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (Check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}