Rockdu's Blog

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

一行，输出最小的L值。

输入输出样例

4
0 1
0 -1
1 0
-1 0

1

说明

数据范围

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

30%的数据，N<=100

50%的数据，N<=2000

100%的数据，N<=20000

这么细节的题居然1A了，感觉手感回来了呀。

题目指名道姓用3个正方形覆盖肯定是有操作的。考虑最靠左的点，最靠上的点，最靠下的点，最靠右的点，有4个，那么其中的两个肯定要被同一个正方形覆盖，而且显然覆盖的最优策略是直接卡在边界上。那么我们直接枚举一次性覆盖哪两个点，将问题转化为用两个正方形去覆盖剩下的点，发现不是一个左上一个右下就是一个左下一个右上。就可以在很大很大常数的O(n log n)内解决这道题。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 2e4 + 5;
const int inf = 0x3f3f3f3f;

struct Point {
    int pos[2];
} pt[maxn];

int mn[2], mx[2], nmn[2], nmx[2], n, vis[maxn];

bool in(const int &x, const int &y, const int &L, const int *pos) {
    return pos[0] <= x + L && pos[0] >= x && pos[1] <= y + L && pos[1] >= y;
}

void del(const int &x, const int &y, const int &L, int & cover) {
    for(register int i = 1; i <= n; ++i)
        if(in(x, y, L, pt[i].pos)) 
            if(!vis[i]) vis[i] = 1, ++cover;
}

void rewM(int * mn, int * mx) {
    mn[0] = mn[1] = inf;
    mx[0] = mx[1] = -inf;
    for(register int i = 1; i <= n; ++i) {
        if(vis[i]) continue;
        mn[0] = min(pt[i].pos[0], mn[0]);
        mn[1] = min(pt[i].pos[1], mn[1]);
        mx[0] = max(pt[i].pos[0], mx[0]);
        mx[1] = max(pt[i].pos[1], mx[1]);
    }
}

bool check2(int x, int y, int L) {
    int cover = 0;
    memset(vis, 0, sizeof(vis));
    del(x, y, L, cover);
    rewM(mn, mx);
    if(cover == n) return 1;
    del(mn[0], mn[1], L, cover);
    if(cover == n) return 1;
    del(mx[0] - L, mx[1] - L, L, cover);
    return cover == n;
}

bool check3(int x, int y, int L) {
    int cover = 0;
    memset(vis, 0, sizeof(vis));
    del(x, y, L, cover);
    rewM(mn, mx);
    if(cover == n) return 1;
    del(mn[0], mx[1] - L, L, cover);
    if(cover == n) return 1;
    del(mx[0] - L, mn[1], L, cover);
    return cover == n;
}

bool check(int L) {
    if(check2(nmn[0], nmn[1], L) || check3(nmn[0], nmn[1], L)) return true;
    if(check2(nmn[0], nmx[1] - L, L) || check3(nmn[0], nmx[1] - L, L)) return true;
    if(check2(nmx[0] - L, nmn[1], L) || check3(nmx[0] - L, nmn[1], L)) return true;
    if(check2(nmx[0] - L, nmx[1] - L, L) || check3(nmx[0] - L, nmx[1] - L, L)) return true;
    return false;
}

int DV(int L, int R) {
    while(L < R - 1) {
        int mid = L + R >> 1;
        if(check(mid)) R = mid;
        else L = mid;
    }
    return R;
}

int main() {
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i)
        scanf("%d%d", &pt[i].pos[0], &pt[i].pos[1]);
    rewM(nmn, nmx);
    printf("%d\n", DV(0, 2000000000));
    return 0;
}