[BZOJ]1052 覆盖问题(HAOI2007)

2023-08-04 20:42:04

　　三矩形覆盖问题啊……不过听说FJOI还出过双圆覆盖问题？

Description

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

Input

　　第一行有一个正整数N，表示有多少棵树。接下来有N行，第i+1行有2个整数Xi,Yi，表示第i棵树的坐标。

Output

　　一行，输出最小的L值。

Sample Input

　　4
　　0 1
　　0 -1
　　1 0
　　-1 0

Sample Output

HINT

　　1 <= N <= 20000，坐标绝对值 <= 10^9，保证不会有2棵树的坐标相同。

Solution

　　三正方形有些复杂，我们不如先从单正方形，双正方形入手。单正方形的答案就是max(横坐标极差,纵坐标极差)。

　　双正方形不好贪心，所以我们二分一下答案，判断两个正方形能否覆盖所有点。

　　我们就思考一下，这两个正方形放在哪里，才能尽量覆盖所有点。

　　发现覆盖的形式不外乎两种情况，一种是一个在左上一个在右下，另一种是一个在右上一个在左下。

　　假设是一个在左上一个在右下的情况，处于左上方的正方形一定要盖住横坐标最左的和纵坐标最上的点，因为另一个正方形不会帮你干这件事。

　　同理，处于右下方的正方形也一样。

　　所以，两个正方形放置的位置也就确定了，剩下的事情就是O(n)扫一遍判断是否在正方形内了。

　　那么三正方形其实也是极其类似的做法。

　　还是二分答案，考虑三个正方形的放法，发现情况有一点多。

　　但是有一点一定是不变的，那就是必定有一个正方形，处于左上、右上、左下、右下的其中一个角！

　　那么我们就枚举这个角，删去这个角内的点，剩下的，就是一个双正方形覆盖问题！

　　时间复杂度O(nlogn)。

#include <cstdio>

#include <algorithm>

#include <cstring>

#define MN 20005

#define INF 0x3FFFFFFF

using namespace std;

struct node{int x,y;}a[MN];

int b[MN];

int bin,n,L,R;

inline int read()

{

    int n=,f=; char c=getchar();

    while (c<'' || c>'') {if(c=='-')f=-; c=getchar();}

    while (c>='' && c<='') {n=n*+c-''; c=getchar();}

    return n*f;

}

bool cov(int len)

{

    if (!bin) return true;

    register int i,lm,rm,dm,um;

    lm=dm=INF; rm=um=-INF;

    for (i=;i<=bin;++i)

        lm=min(lm,a[b[i]].x),rm=max(rm,a[b[i]].x),

        dm=min(dm,a[b[i]].y),um=max(um,a[b[i]].y);

    for (i=;i<=bin;++i)

        if (!(a[b[i]].x<=lm+len&&a[b[i]].y<=dm+len

            ||a[b[i]].x>=rm-len&&a[b[i]].y>=um-len)) break;

    if (i>bin) return true;

    for (i=;i<=bin;++i)

        if (!(a[b[i]].x<=lm+len&&a[b[i]].y>=um-len

            ||a[b[i]].x>=rm-len&&a[b[i]].y<=dm+len)) break;

    if (i>bin) return true;

    return false;

}

void del(int lm,int dm,int rm,int um)

{

    register int i;

    for (bin=,i=;i<=n;++i)

        if (a[i].x<lm||a[i].x>rm||a[i].y<dm||a[i].y>um) b[++bin]=i;

}

int main()

{

    register int i,lm,rm,dm,um;

    lm=dm=INF; rm=um=-INF;

    n=read();

    for (i=;i<=n;++i)

        a[i].x=read(),a[i].y=read(),

        lm=min(lm,a[i].x),rm=max(rm,a[i].x),

        dm=min(dm,a[i].y),um=max(um,a[i].y);

    L=; R=max(um-dm,rm-lm);

    while (L<R)

    {

        int mid=L+R>>;

        for (i=;i<=;++i)

        {

                 if (i==) del(lm,dm,lm+mid,dm+mid);

            else if (i==) del(lm,um-mid,lm+mid,um);

            else if (i==) del(rm-mid,dm,rm,dm+mid);

            else if (i==) del(rm-mid,um-mid,rm,um);

            if (cov(mid)) break;

        }

        if (i<=) R=mid; else L=mid+;

    }

    printf("%d",L);

}

Last Word

　　没有想到小C能抢到这题的一个rank1，先放张图留念，指不定哪天就被某大神艹下去了。

码农公寓