洛谷 P2218 [HAOI2007]覆盖问题解题报告

P2218 [HAOI2007]覆盖问题

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

一行，输出最小的(L)值。

说明

数据范围

(100\%)的数据，(-1,000,000,000<=X_i,Y_i<=1,000,000,000)

(30\%)的数据，(N<=100)

(50\%)的数据，(N<=2000)

(100\%)的数据，(N<=20000)

一道思路自然，感觉解法非常有道理但是想不到的题目（其实是我太菜）

二分答案+贪心或枚举放正方形，一般都可以想到这里来

然后怎么放呢。。。

考虑一些看起来非常容易忽视的条件

“(3)个(L*L)的正方形的边要求平行于坐标轴”

“3个”、“平行于坐标轴”

这是两个关键词

坐标轴是相互垂直的，那么如果我们用一个矩性围住点集，我们惊奇的发现，这个矩形是唯一的。

这里可能是比较跳跃，但是多试多换思路，其实是可能想到的。

然后“3个”正方形，我们发现矩形的每条边都需要和正方形的相接，因为边上必有点需要覆盖

因为矩形有四个边，我们发现有一个正方形必须去填角。

枚举！

然后只有两个正方形，而且剩余点集构成子问题

递归求解！

因为状态数非常少，所以很显然可过

总结一下，没什么思路的时候不妨多分析分析题目条件的特殊性究竟有什么意义，哪怕没什么感觉也多试几个想法

Code:

#include <cstdio>
#include <cstring>
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
const int N=20010;
const int inf=0x3f3f3f3f;
int dx[N],dy[N],used[N],l,r,up,down,n;
void get()
{
    l=down=inf,r=up=-inf;
    for(int i=1;i<=n;i++)
    {
        if(used[i]) continue;
        l=min(l,dx[i]),r=max(r,dx[i]);
        down=min(down,dy[i]),up=max(up,dy[i]);
    }
}
bool check(int len,int rest)
{
    get();
    if(rest==1) return len>=max(r-l,up-down);
    int l0=l,r0=r,up0=up,down0=down,flag=0,vis[N];
    for(int i=1;i<=n;i++) vis[i]=used[i];

    for(int i=1;i<=n;i++)
        if(dx[i]>=l0&&dy[i]<=up0&&dx[i]<=l0+len&&dy[i]>=up0-len)
            used[i]=1;
    flag=max(flag,check(len,rest-1));

    for(int i=1;i<=n;i++) used[i]=vis[i];
    for(int i=1;i<=n;i++)
        if(dx[i]>=l0&&dy[i]>=down0&&dx[i]<=l0+len&&dy[i]<=down0+len)
            used[i]=1;
    flag=max(flag,check(len,rest-1));

    for(int i=1;i<=n;i++) used[i]=vis[i];
    for(int i=1;i<=n;i++)
        if(dx[i]<=r0&&dy[i]<=up0&&dx[i]>=r0-len&&dy[i]>=up0-len)
            used[i]=1;
    flag=max(flag,check(len,rest-1));

    for(int i=1;i<=n;i++) used[i]=vis[i];
    for(int i=1;i<=n;i++)
        if(dx[i]<=r0&&dy[i]>=down0&&dx[i]>=r0-len&&dy[i]<=down0+len)
            used[i]=1;
    flag=max(flag,check(len,rest-1));
    return flag;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",dx+i,dy+i);
    get();
    int L=1,R=max(r-l,up-down);
    while(L<R)
    {
        int mid=L+R>>1;
        memset(used,0,sizeof(used));
        if(check(mid,3))
            R=mid;
        else
            L=mid+1;
    }
    printf("%d
",L);
    return 0;
}

2018.8.10

洛谷 P2218 [HAOI2007]覆盖问题 解题报告