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

作者: wjyyy 分类: 二分,枚举,解题报告,贪心 发布时间: 2018-08-10 16:33

点击量:62

 

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

 

题目描述

某人在山上种了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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */