【bzoj1052】[HAOI2007]覆盖问题

2015.05.26 16:47 Tue | 18次阅读 | 旧日oi | 固定链接 | 源码

题目大意:给定二维平面上一些点,用3个L*L的正方形(长宽平行坐标轴)覆盖所有点,求L的最小值。n<=20000
题解
首先一定是二分答案,问题在于如何check。
先用一个大矩形将所有点括起来,直观的想,一定会有一个三角形在大矩形的角上,然而如果是用4个的话就不一定了,可以画一画理解一下。
然后我们可以枚举四个角,删掉内部的点后,再重复一遍上面的过程就可以了。

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
struct node{
    int x[20005],y[20005];
    int top;
}a;
int l,r,mid,ans;
void cut(node &a,int x,int y,int xx,int yy)
{
    int cnt=0;
    for(int i=1;i<=a.top;i++)
    {
        if(a.x[i]<x||a.x[i]>xx||a.y[i]<y||a.y[i]>yy)
        a.x[++cnt]=a.x[i],a.y[cnt]=a.y[i];
    }
    a.top=cnt;
}
void solve(node &a,int k)
{
    int x=inf,y=inf,xx=-inf,yy=-inf;
    for(int i=1;i<=a.top;i++)
    {
        x=min(x,a.x[i]);y=min(y,a.y[i]);
        xx=max(xx,a.x[i]);yy=max(yy,a.y[i]);
    }   
    if(k==1) cut(a,x,y,x+mid,y+mid);
    if(k==2) cut(a,xx-mid,y,xx,y+mid);
    if(k==3) cut(a,x,yy-mid,x+mid,yy);
    if(k==4) cut(a,xx-mid,yy-mid,xx,yy);
}
bool check()
{
    node b;
    for(int i=1;i<=4;i++)
    for(int j=1;j<=4;j++)
    {
        b=a;
        solve(b,i);solve(b,j);
        int x=inf,y=inf,xx=-inf,yy=-inf;
        for(int k=1;k<=b.top;k++)
        {
            x=min(x,b.x[k]);y=min(y,b.y[k]);
            xx=max(xx,b.x[k]);yy=max(yy,b.y[k]);
        }   
        if(xx-x<=mid&&yy-y<=mid) return 1;
    }
    return 0;
}
int main()
{
    cin>>a.top;
    for(int i=1;i<=a.top;i++) scanf("%d%d",&a.x[i],&a.y[i]);
    l=1,r=inf;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check()) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans<<endl;
}```