洛谷 P2218 [HAOI2007]覆盖问题 题解【贪心】【二分答案】【构造】

点击量：244

    正常人都不会往这个地方想吧。。。随手想出正解的是什么怪物

目录

题目描述

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

输入输出格式

输入格式：

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

 

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

 

输出格式：

一行，输出最小的L值。

 

输入输出样例

输入样例#1：

4
0 1
0 -1
1 0
-1 0

输出样例#1：

1

说明

数据范围

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

 

30%的数据，N<=100

 

50%的数据，N<=2000

 

100%的数据，N<=20000

题解：

    这个题的二分答案应该很好想，只不过check怎么写真的不知道从哪入手。而且不知道为什么就是三个正方形。

    因为我们要覆盖图上所有的点，所以我们先处理出横坐标最大/最小、纵坐标最大/最小的点。用这些点当作四个边界，围出一个最小覆盖矩形。这个矩形四条边上一定都有点，不然不可能成为边界。而我们只有三个正方形，说明一定有一个小正方形在矩形的一个角上，包揽了处于这两条邻边的极限点。需要先处理出放在哪些角，再考虑还剩两个正方形的情况。

    因为已经使用了一个正方形并作出了贡献，所以剩下的最小覆盖矩形就会变小。而我们现在还剩两个正方形，就需要至少一个管一对邻边。这时我们再枚举当前正方形放在哪个对角，再看剩下的点组成的最小覆盖正方形边长是多少，如果仍然小于check的值，就说明合法。

    就像上图，我们枚举第一个正方形放在左上角，那么第二步就到了右边这种情况。接着我们继续枚举新矩形的四角，再清理一个正方形，最后再枚举一遍就可以了。

    时间复杂度为$ O(4^2n)$。

Code：（mxxmxy太多了特别容易弄混。。。）

#include<cstdio>
#include<cstring>
int x[21000],y[21000];
int used[21000];
int n;
int mnx=1000000000,mny=1000000000;
int mxx=-1000000000,mxy=-1000000000;
bool check2(int t)//第三个正方形
{
    int _mnx=1000000000,_mny=1000000000;
    int _mxx=-1000000000,_mxy=-1000000000;
    for(int i=1;i<=n;i++)
        if(!used[i])
        {
            _mnx=_mnx<x[i]?_mnx:x[i];
            _mxx=_mxx>x[i]?_mxx:x[i];
            _mny=_mny<y[i]?_mny:y[i];
            _mxy=_mxy>y[i]?_mxy:y[i];
        }
    return _mxx-_mnx<=t&&_mxy-_mny<=t;
}
bool check1(int t)//第二个正方形
{
    int mnX=1000000000,mnY=1000000000;
    int mxX=-1000000000,mxY=-1000000000;
    for(int i=1;i<=n;i++)
        if(!used[i])
        {
            mnX=mnX<x[i]?mnX:x[i];
            mxX=mxX>x[i]?mxX:x[i];
            mnY=mnY<y[i]?mnY:y[i];
            mxY=mxY>y[i]?mxY:y[i];
        }
    //左上角
    for(int i=1;i<=n;i++)
        if(!used[i]&&x[i]-mnX<=t&&mxY-y[i]<=t)
            used[i]=-1;
    if(check2(t))
        return true;
    for(int i=1;i<=n;i++)
        if(used[i]==-1)
            used[i]=0;
    //右上角
    for(int i=1;i<=n;i++)
        if(!used[i]&&mxY-x[i]<=t&&mxY-y[i]<=t)
            used[i]=-1;
    if(check2(t))
        return true;
    for(int i=1;i<=n;i++)
        if(used[i]==-1)
            used[i]=0;
    //左下角
    for(int i=1;i<=n;i++)
        if(!used[i]&&x[i]-mnX<=t&&y[i]-mnY<=t)
            used[i]=-1;
    if(check2(t))
        return true;
    for(int i=1;i<=n;i++)
        if(used[i]==-1)
            used[i]=0;
    //右下角
    for(int i=1;i<=n;i++)
        if(!used[i]&&mxX-x[i]<=t&&y[i]-mnY<=t)
            used[i]=-1;
    if(check2(t))
        return true;
    return false;
}
bool check(int t)//第一个正方形
{
    memset(used,0,sizeof(used));
    //左上角(笛卡尔坐标系)
    for(int i=1;i<=n;i++)
        if(x[i]-mnx<=t&&mxy-y[i]<=t)
            used[i]=1;
    if(check1(t))
        return true;
    memset(used,0,sizeof(used));
    //右上角
    for(int i=1;i<=n;i++)
        if(mxx-x[i]<=t&&mxy-y[i]<=t)
            used[i]=1;
    if(check1(t))
        return true;
    memset(used,0,sizeof(used));
    //左下角
    for(int i=1;i<=n;i++)
        if(x[i]-mnx<=t&&y[i]-mny<=t)
            used[i]=1;
    if(check1(t))
        return true;
    memset(used,0,sizeof(used));
    //右下角
    for(int i=1;i<=n;i++)
        if(mxx-x[i]<=t&&y[i]-mny<=t)
            used[i]=1;
    if(check1(t))
        return true;
    return false;
}
int main()
{

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        mnx=mnx<x[i]?mnx:x[i];
        mxx=mxx>x[i]?mxx:x[i];
        mny=mny<y[i]?mny:y[i];
        mxy=mxy>y[i]?mxy:y[i];
    }
    int l=0,r=(mxy-mny)>(mxx-mnx)?(mxy-mny):(mxx-mnx),mid;
    while(l<r)
    {
        mid=l+r>>1;
        if(check(mid))
            r=mid;
        else
            l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}