题目传送门：【BZOJ 1052】
题目大意：某人在山上种了 N 棵小树苗。冬天来了，温度急速下降，小树苗脆弱得不堪一击，他决定用 3 个 L * L 的正方形塑料薄膜将小树遮起来。 我们将山建立一个平面直角坐标系，设第 i 棵小树的坐标为（Xi , Yi ），3 个 L * L 的正方形的边要求平行与坐标轴，一个点如果在正方形的边界上，也算作被覆盖。当然，我们希望塑料薄膜面积越小越好，即求 L 最小值。
题目分析：
这道题的解题思路比较容易想到。不过我用的搜索，对于这种类型嘛……我一向做搜索题都做得——超超超超超级复杂，在此表示如果有神犇或 dalao 觉得我代码丑的请轻喷╮(╯▽╰)╭
首先，看到“求薄膜能够覆盖完所有树苗的面积的最小值”时，直接想到二分膜的面积。我们把每棵树看成一个点，先用一个矩形将所有的点包围起来，这样便确定了二分上界。
判断时，首先我们将第一个薄膜放在四个角中的一个角上（这样可以保证放的是最优的，因为这样能尽量多地覆盖位于矩形边上的点）。在放第二块薄膜时，我们以同样的操作，先用一个矩形将剩下未被覆盖的点包围起来，然后像之前那样，将第二块薄膜放在新矩形四个角中的一个角上。对于第三块膜，我们直接判断最后所有剩下的点的横纵坐标能否被第三块膜覆盖完，如果能，则将面积缩小并继续查找；否则增大膜的面积。
.
这道题我写了 240 行，5000 多字节的代码…… 看到其他好多人 80 行解决问题…… 果然我搜索还是写的不好……不过还是跑得比较快……
下面附上代码：
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int MX=20005; const int INF=0x3f3f3f3f; struct Point{ int x,y; int vis; Point(){x=y=0,vis=0;} }; Point map[MX]; //保存每个点的坐标以及是否被覆盖 int n; bool check(int s){ for (int i=1;i<=n;i++){ //初始化 map[i].vis=0; } /***************************第一层开始***************************************/ int mr=-INF,ml=INF,mu=-INF,md=INF; //mr:右边的界限 right ml:左边的界限 left //mu:上边的界限 up md:下边的界限 down for (int i=1;i<=n;i++){ if (map[i].x > mr) mr=map[i].x; if (map[i].x < ml) ml=map[i].x; if (map[i].y > mu) mu=map[i].y; if (map[i].y < md) md=map[i].y; } for (int i=1;i<=4;i++){ //放置第一块，枚举四个角 switch (i){ case 1:{ for (int j=1;j<=n;j++){ if (map[j].x >= ml && map[j].x <= ml+s && map[j].y <= mu && map[j].y >= mu-s){ map[j].vis++; } } break; } case 2:{ for (int j=1;j<=n;j++){ if (map[j].x <= mr && map[j].x >= mr-s && map[j].y <= mu && map[j].y >= mu-s){ map[j].vis++; } } break; } case 3:{ for (int j=1;j<=n;j++){ if (map[j].x >= ml && map[j].x <= ml+s && map[j].y >= md && map[j].y <= md+s){ map[j].vis++; } } break; } case 4:{ for (int j=1;j<=n;j++){ if (map[j].x <= mr && map[j].x >= mr-s && map[j].y >= md && map[j].y <= md+s){ map[j].vis++; } } break; } } /*--------------------------第二层开始--------------------------------------*/ int mmr=-INF,mml=INF,mmu=-INF,mmd=INF; for (int k=1;k<=n;k++){ if (!map[k].vis){ if (map[k].x > mmr) mmr=map[k].x; if (map[k].x < mml) mml=map[k].x; if (map[k].y > mmu) mmu=map[k].y; if (map[k].y < mmd) mmd=map[k].y; } } for (int j=1;j<=4;j++){ //放置第二块 switch (j){ case 1:{ for (int p=1;p<=n;p++){ if (map[p].x >= mml && map[p].x <= mml+s && map[p].y <= mmu && map[p].y >= mmu-s){ map[p].vis++; } } break; } case 2:{ for (int p=1;p<=n;p++){ if (map[p].x <= mmr && map[p].x >= mmr-s && map[p].y <= mmu && map[p].y >= mmu-s){ map[p].vis++; } } break; } case 3:{ for (int p=1;p<=n;p++){ if (map[p].x >= mml && map[p].x <= mml+s && map[p].y >= mmd && map[p].y <= mmd+s){ map[p].vis++; } } break; } case 4:{ for (int p=1;p<=n;p++){ if (map[p].x <= mmr && map[p].x >= mmr-s && map[p].y >= mmd && map[p].y <= mmd+s){ map[p].vis++; } } break; } } /*==========================第三层开始======================================*/ int mmmr=-INF,mmml=INF,mmmu=-INF,mmmd=INF; bool no_others=true; for (int q=1;q<=n;q++){ //放置第三块 if (!map[q].vis){ no_others=false; if (map[q].x > mmmr) mmmr=map[q].x; if (map[q].x < mmml) mmml=map[q].x; if (map[q].y > mmmu) mmmu=map[q].y; if (map[q].y < mmmd) mmmd=map[q].y; } } if ((abs(mmmr-mmml) <= s && abs(mmmu-mmmd) <= s) || no_others) return true; /*==========================第三层结束======================================*/ switch (j){ case 1:{ for (int p=1;p<=n;p++){ if (map[p].x >= mml && map[p].x <= mml+s && map[p].y <= mmu && map[p].y >= mmu-s){ map[p].vis--; } } break; } case 2:{ for (int p=1;p<=n;p++){ if (map[p].x <= mmr && map[p].x >= mmr-s && map[p].y <= mmu && map[p].y >= mmu-s){ map[p].vis--; } } break; } case 3:{ for (int p=1;p<=n;p++){ if (map[p].x >= mml && map[p].x <= mml+s && map[p].y >= mmd && map[p].y <= mmd+s){ map[p].vis--; } } break; } case 4:{ for (int p=1;p<=n;p++){ if (map[p].x <= mmr && map[p].x >= mmr-s && map[p].y >= mmd && map[p].y <= mmd+s){ map[p].vis--; } } break; } } /*--------------------------第二层结束--------------------------------------*/ } switch (i){ case 1:{ for (int j=1;j<=n;j++){ if (map[j].x >= ml && map[j].x <= ml+s && map[j].y <= mu && map[j].y >= mu-s){ map[j].vis--; } } break; } case 2:{ for (int j=1;j<=n;j++){ if (map[j].x <= mr && map[j].x >= mr-s && map[j].y <= mu && map[j].y >= mu-s){ map[j].vis--; } } break; } case 3:{ for (int j=1;j<=n;j++){ if (map[j].x >= ml && map[j].x <= ml+s && map[j].y >= md && map[j].y <= md+s){ map[j].vis--; } } break; } case 4:{ for (int j=1;j<=n;j++){ if (map[j].x <= mr && map[j].x >= mr-s && map[j].y >= md && map[j].y <= md+s){ map[j].vis--; } } break; } } } /***************************第一层结束***************************************/ return false; } int main(){ int pa,pb,mr=0,mu=0,ml=0,md=0,lf=0,rt=0,mid=0; //rt:上界 lf:下界 cin>>n; for (int i=1;i<=n;i++){ cin>>pa>>pb; map[i].x=pa,map[i].y=pb; if (i>=2){ if (pa>mr) mr=pa; if (pa<ml) ml=pa; if (pb>mu) mu=pb; if (pb<md) md=pb; } else { ml=mr=pa,mu=md=pb; } } rt=max(abs(mr-ml),abs(mu-md)); while (rt-lf>=1){ mid=(lf+rt)/2; if (check(mid)){ rt=mid; } else { lf=mid+1; } } printf("%d",lf); return 0; }