BZOJ1052【HAOI2007】覆盖问题 <二分答案>

Posted on Symbols count in article: 793 Reading time ≈ 3 mins.

Problem

【HAOI2007】覆盖问题

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

某人在山上种了NN棵小树苗。冬天来了，温度急速下降，小树苗脆弱得不堪一击，于是树主人想用一些塑料薄膜把这些小树遮盖起来，经过一番长久的思考，他决定用33个L×LL\times L的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系，设第ii棵小树的坐标为(Xi,Yi)(X_i,Y_i)，33个L×LL\times L的正方形的边要求平行与坐标轴，一个点如果在正方形的边界上，也算作被覆盖。当然，我们希望塑料薄膜面积越小越好，即求L最小值。

Input

第一行有一个正整数NN，表示有多少棵树。
接下来有NN行，第i+1i+1行有22个整数Xi,YiX_i,Y_i，表示第ii棵树的坐标，保证不会有22个树的坐标相同。

Output

一行，输出最小的LL值。

Sample Input

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

Sample Output

1
1

HINT

100%100\%的数据，N≤2×104N\le2\times10^4

标签：二分答案

Solution

二分水题。

考虑到当LL大于等于答案时，一定能全部覆盖。因此可以二分答案。
对于当前二分到的答案tanstans，贪心选取前两个正方形，然后判断剩下的点能否被一个正方形包住。
贪心选取即每个正方形一定覆盖剩余点中左上、左下、右上、右下四个最远点中至少一个，因而枚举1616种情况后判断即可。

Code

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
#include <bits/stdc++.h>
#define x first
#define y second
#define mp make_pair
#define pii pair<int,int>
#define MAX_N 20000
#define INF 0x3f3f3f
#define mid ((l+r)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n;    pii p[MAX_N+5];	bool mrk[MAX_N+5];
bool chk(int r) {
    int x1 = INF, y1 = INF, x2 = -INF, y2 = -INF;
    for (int i = 1; i <= n; i++) if (!mrk[i])
        x1 = min(x1, p[i].x), y1 = min(y1, p[i].y), 
        x2 = max(x2, p[i].x), y2 = max(y2, p[i].y);
    return x2-x1 <= r && y2-y1 <= r;
}
int del(int sx, int sy, int r) {
    int ret = 0;
    for (int i = 1; i <= n; i++) if (!mrk[i])
        if (p[i].x >= sx && p[i].x <= sx+r) 
            if (p[i].y >= sy && p[i].y <= sy+r)
                mrk[i] = true, ret++;
    return ret;
}
bool DFS(int stp, int lft, int r) {
    if (!lft) return true;
    if (stp > 2) return chk(r);
    int x1 = INF, y1 = INF, x2 = -INF, y2 = -INF;
    for (int i = 1; i <= n; i++) if (!mrk[i])
        x1 = min(x1, p[i].x), y1 = min(y1, p[i].y), 
        x2 = max(x2, p[i].x), y2 = max(y2, p[i].y);
    bool bk[MAX_N+5];	memcpy(bk, mrk, sizeof mrk);
    if (DFS(stp+1, lft-del(x1, y1, r), r)) return true;		memcpy(mrk, bk, sizeof bk);
    if (DFS(stp+1, lft-del(x1, y2-r, r), r)) return true;	memcpy(mrk, bk, sizeof bk);
    if (DFS(stp+1, lft-del(x2-r, y1, r), r)) return true;	memcpy(mrk, bk, sizeof bk);
    if (DFS(stp+1, lft-del(x2-r, y2-r, r), r)) return true;	memcpy(mrk, bk, sizeof bk);
    return false;
}
int bi_search(int l, int r) {
    int ret = -1;
    while (l <= r) {
        memset(mrk, false, sizeof mrk);
        if (!DFS(1, n, mid)) l = mid+1;
        else ret = mid, r = mid-1;
    }
    return ret;
}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(p[i].x), read(p[i].y);
    return printf("%d\n", bi_search(1, INF)), 0;
}