首页 > 代码库 > bzoj1052

bzoj1052

2024-08-24 02:34:32   219人阅读

Description

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

Input

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

Output

　　一行，输出最小的L值。

Sample Input

4
0 1
0 -1
1 0
-1 0

Sample Output

1

HINT

100%的数据，N<=20000

题解

每次对于一些点，我们把它们用一个最小的长方形框起来，把正方形放在四角之一

然后就产生了一个子问题，显然这样做是最优的

二分即可

#include<stdio.h>
#include<iostream>
#define inf 1000000000
#define il inline
using namespace std;
const int N=30001;
struct P{int x,y;} a[N];
int n,chk[N];
il void cover(int d,int u,int l,int r,int k){
    for(int i=1;i<=n;i++) if(chk[i]==0){
        if(l<=a[i].x&&a[i].x<=r&&d<=a[i].y&&a[i].y<=u){
            chk[i]=k;
        }       
    }
}
il void uncover(int k){
    for(int i=1;i<=n;i++) 
        if(chk[i]==k){
            chk[i]=0;
        }
}
il bool fulfill(){
    for(int i=1;i<=n;i++)
        if(chk[i]==0) return 0;
    return 1;
}
il int dfs(int k,int lim){
    if(fulfill()) return true;
    if(k==4) return false;
    int u=-inf,d=inf,l=inf,r=-inf,flag=0;
    for(int i=1;i<=n;i++){
        if(chk[i]==0){
            u=max(u,a[i].y);
            d=min(d,a[i].y);
            l=min(l,a[i].x);
            r=max(r,a[i].x);
        }
    }
    /*cout<<k<<" "<<lim<<endl;
    for(int i=1;i<=n;i++)
        cout<<chk[i]<<" ";
    cout<<endl;
    cout<<l<<" "<<r<<" "<<d<<" "<<u<<endl;
    system("pause");*/
    cover(d,d+lim,l,l+lim,k);
    if(dfs(k+1,lim)) flag=1;
    uncover(k);
    cover(d,d+lim,r-lim,r,k);
    if(dfs(k+1,lim)) flag=1;
    uncover(k);
    cover(u-lim,u,r-lim,r,k);
    if(dfs(k+1,lim)) flag=1;
    uncover(k);
    cover(u-lim,u,l,l+lim,k);
    if(dfs(k+1,lim)) flag=1;
    uncover(k);
    return flag;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    int l=0,r=inf,mid;
    while(l<r){
        mid=(l+r)/2;
        if(dfs(1,mid)) r=mid;
        else l=mid+1;
    }
    cout<<r;
    return 0;
}

 

bzoj1052


联系
我们