bzoj1052-HAOI2007 覆盖问题

• 题面描述
  • 某人在山上种了\(N\leq 2*10^4?\)棵小树苗。冬天来了，温度急速下降，小树苗脆弱得不堪一击，于是树主人想用一些塑料薄膜把这些小树遮盖起来，经过一番长久的思考，他决定用\(3?\)个\(L*L?\)的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系，设第\(i?\)棵小树的坐标为\((x_i,y_i)?\)，\(3?\)个\(L*L?\)的正方形的边要求平行与坐标轴，一个点如果在正方形的边界上，也算作被覆盖。当然，我们希望塑料薄膜面积越小越好，即求\(L?\)最小值。
• 输入格式
  • 第一行有一个正整数\(N\)，表示有多少棵树。接下来有\(N\)行，第\(i+1\)行有\(2\)个整数\(x_i,y_i\)，表示第\(i\)棵树的坐标，保证不会有\(2\)个树的坐标相同。
• 输出格式
  • 一行，输出最小的\(L\)值。
• 题解
  • 先对给定的坐标\((x_i,y_i)\)，找到恰好覆盖这些坐标的一个大矩形。
  • 首先，这个大矩形的四个边上必然都存在一个点，故大矩形边上至少有\(4\)个点。根据 抽屉原理，\(4\)个点要被\(3\)个小矩形覆盖其中必然有\(2\)个点被同一个矩阵覆盖。也就意味着，这个大矩形的\(4\)个顶角中必然有一个顶角被一个小矩形覆盖。
  • 因此，我们可以先二分\(L\)，对于每个\(L\)，枚举其中第一个小矩形覆盖哪一个大矩形的顶角。把问题划归为一个更小的子问题（用两个小矩形覆盖一些点）。再利用同样的技巧，对第二个小矩形（边长同样为\(L\)）枚举它覆盖剩余点围成的大矩形的那个顶角。
  • 最后对于剩下的点判定能被第三个\(L*L\)的小矩形完全覆盖

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2e4+5;
struct rec{
    int x,y;
} a[MAXN],b[5],c[5];
int n,up,dn,rig,lef;
bool use[MAXN],res[MAXN];
bool solve(int L){
    up=dn=rig=lef=0;
    for (int i=1;i<=n;i++){
        if (use[i]) continue;
        if (a[up].y<a[i].y||up==0) up=i;
        if (a[dn].y>a[i].y||dn==0) dn=i;
        if (a[rig].x<a[i].x||rig==0) rig=i;
        if (a[lef].x>a[i].x||lef==0) lef=i;
    }
    if (up==0) return 1;
    c[1]=(rec){a[lef].x,a[up].y};
    c[2]=(rec){a[rig].x,a[up].y};
    c[3]=(rec){a[rig].x,a[dn].y};
    c[4]=(rec){a[lef].x,a[dn].y};
//  cout<<"sol2:"<<endl;
//  for (int i=1;i<=4;i++){
//      cout<<" "<<i<<" "<<c[i].x<<" "<<c[i].y<<endl;
//  }
    bool flag=0;
    for (int i=1;i<=4;i++){
//      cout<<" tp2: "<<i<<endl;
        int dx=1,dy=1;
        if (i==1) dy=-1;
        if (i==2) dx=-1,dy=-1;
        if (i==3) dx=-1;
        int x=c[i].x,y=c[i].y;
        int nx=x+dx*L,ny=y+dy*L;
        int xl=min(x,nx),xr=max(x,nx);
        int yl=min(y,ny),yr=max(y,ny);
        for (int j=1;j<=n;j++) res[j]=use[j];
//      cout<<" cvr2: ";
        for (int j=1;j<=n;j++){
            if (res[j]) continue;
            if (a[j].x<xl||a[j].x>xr) continue;
            if (a[j].y<yl||a[j].y>yr) continue;
            res[j]=1;// cout<<j<<" ";
        }
//      cout<<endl;
        up=dn=lef=rig=0;
        for (int j=1;j<=n;j++){
            if (res[j]) continue;
            if (a[up].y<a[j].y||up==0) up=j;
            if (a[dn].y>a[j].y||dn==0) dn=j;
            if (a[lef].x>a[j].x||lef==0) lef=j;
            if (a[rig].x<a[j].x||rig==0) rig=j;
        }
        if (up==0) return 1;
        int tmp=max(a[up].y-a[dn].y,a[rig].x-a[lef].x);
//      cout<<" endLen: "<<tmp<<endl;
        flag|=(tmp<=L);
    }
    return flag;
}
bool check(int L){
    bool flag=0;
    for (int i=1;i<=4;i++){
//      cout<<L<<" tp: "<<i<<endl;
        int dx=1,dy=1;
        if (i==1) dy=-1;
        if (i==2) dx=-1,dy=-1;
        if (i==3) dx=-1;
        int x=b[i].x,y=b[i].y;
        int nx=x+dx*L,ny=y+dy*L;
        int xl=min(x,nx),xr=max(x,nx);
        int yl=min(y,ny),yr=max(y,ny);
//      cout<<"cvr: ";
        for (int j=1;j<=n;j++){
            use[j]=0;
            if (a[j].x<xl||a[j].x>xr) continue;
            if (a[j].y<yl||a[j].y>yr) continue;
            use[j]=1;// cout<<j<<" ";
        }
//      cout<<endl;
//      cout<<"flg: "<<solve(L)<<endl;
        flag|=solve(L);
    }
    return flag;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    for (int i=1;i<=n;i++){
        if (a[up].y<a[i].y||up==0) up=i;
        if (a[dn].y>a[i].y||dn==0) dn=i;
        if (a[rig].x<a[i].x||rig==0) rig=i;
        if (a[lef].x>a[i].x||lef==0) lef=i;
    }
    b[1]=(rec){a[lef].x,a[up].y};
    b[2]=(rec){a[rig].x,a[up].y};
    b[3]=(rec){a[rig].x,a[dn].y};
    b[4]=(rec){a[lef].x,a[dn].y};
//  for (int i=1;i<=4;i++){
//      cout<<i<<" "<<b[i].x<<" "<<b[i].y<<endl;
//  }
//  cout<<endl;
    int l=0,r=max(a[up].y-a[dn].y,a[rig].x-a[lef].x),mid;
    while (l+1<r){
        mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid;
    }
    printf("%d\n",r);
    return 0;
}

bzoj1052-HAOI2007 覆盖问题

原文：https://www.cnblogs.com/shjrd-dlb/p/10735361.html