1052: [HAOI2007]覆盖问题
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 0Sample Output
1HINT
100%的数据，N<=20000
Source
【分析】
为什么黄学长称之为贪心。。？不懂。。
首先我们用一个最小的矩形把所有点框住（这个很容易求吧？），
如果答案的正方形边长等于这个矩形的宽，那么肯定有两个正方形是推到两边的，就是至少有一个正方形的顶点是矩形的顶点。
如果正方形边长小于宽，因为矩形每条边至少有一个点，所以一定有一个正方形覆盖了矩形两条边，那么这个至少也有一个正方形的顶点是矩形的顶点。
大于宽就不用说了吧？
那么我们先二分答案，然后就枚举矩形的四个角，把覆盖的点删掉，递归做子问题就可以了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 20010
#define INF 0xfffffff int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} struct node
{
int x,y;
int p;
}t[Maxn]; int n,tot; void change(int x,int y,int nw,int L)
{
for(int i=;i<=n;i++) if(t[i].x>=x&&t[i].y>=y&&t[i].p==)
{
if(t[i].x-x>L||t[i].y-y>L) continue;
t[i].p=nw;tot--;
}
} void change2(int nw)
{
for(int i=;i<=n;i++) if(t[i].p==nw)
{
t[i].p=;
tot++;
}
} bool check(int L,int nw)
{
if(tot==) return ;
int x1=INF,x2=-INF,y1=INF,y2=-INF;
for(int i=;i<=n;i++) if(t[i].p==)
{
x1=mymin(x1,t[i].x);x2=mymax(x2,t[i].x);
y1=mymin(y1,t[i].y);y2=mymax(y2,t[i].y);
}
if(nw==) return mymax(x2-x1,y2-y1)<=L;
int nx,ny;
bool ok=;
nx=x1,ny=y1;change(nx,ny,nw,L);
if(check(L,nw-)) ok=;change2(nw);
if(ok) return ; nx=x1,ny=y2-L;change(nx,ny,nw,L);
if(check(L,nw-)) ok=;change2(nw);
if(ok) return ; nx=x2-L,ny=y1;change(nx,ny,nw,L);
if(check(L,nw-)) ok=;change2(nw);
if(ok) return ; nx=x2-L,ny=y2-L;change(nx,ny,nw,L);
if(check(L,nw-)) ok=;change2(nw);
if(ok) return ;
return ;
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&t[i].x,&t[i].y);
t[i].p=;
}
int l=,r=INF;
tot=n;
while(l<r)
{
int mid=(l+r)>>;
if(check(mid,)) r=mid;
else l=mid+;
}
printf("%d\n",l);
return ;
}
2017-02-22 14:07:58