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 0
Sample Output
1
HINT
100%的数据，N<=20000
我发现，似乎经过优化快了很多的我都会写博客。额……好吧。
这道题在当时模拟ACM时，便已判断为二分答案O（lg n）*check O(n)。但
是，当时并没有想到怎么去check，现在便可以说了。
我们一共只有3张布，但所有点可以确定一个矩形，共四条边。即意味着肯定
有布覆盖了多条边。而越界的布是没有实际意义的，所以我们可以枚举矩形的四
个角。然后递归下去，处理干净。（贪心+DFS）
这里有两份代码，速度有很大区别。
1 /************************************************************** 2 Problem: 1052 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:760 ms 7 Memory:1056 kb 8 ****************************************************************/ 9 10 #include11 #include 12 #include 13 template inline void readin(T &res) {14 static char ch;T flag=1;15 while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;16 res=ch-48;while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;res*=flag;17 }18 const int N = 20010;19 const int inf = 0x3f3f3f3f;20 struct Point { int x,y;}points[N];21 int n, vis[N];22 int DFS(int L,int siz) {23 if(siz==0) {24 for( int i = 1; i <= n; i++ ) if(!vis[i]) return 0;25 return 1;26 }27 int xx[2], yy[2];28 xx[0]=yy[0]=inf;xx[1]=yy[1]=-inf;29 for( int i = 1; i <= n; i++ ) if(!vis[i]) {30 xx[0]=std::min(xx[0],points[i].x);xx[1]=std::max(xx[1],points[i].x);31 yy[0]=std::min(yy[0],points[i].y);yy[1]=std::max(yy[1],points[i].y);32 }33 for( int i = 0; i <= 1; i++ ) for( int j = 0; j <= 1; j++ ) {34 for( int k = 1; k <= n; k++ ) if(!vis[k]&&std::max(abs(points[k].x-xx[i]),abs(points[k].y-yy[j]))<=L) vis[k]=siz;35 if(DFS(L,siz-1)) return 1;36 for( int k = 1; k <= n; k++ ) if(vis[k]==siz) vis[k]=0;37 }38 return 0;39 }40 int main() {41 readin(n);42 int mx=inf, my=inf, Mx=-inf, My=-inf;43 for( int i = 1; i <= n; i++ ) {44 readin(points[i].x), readin(points[i].y);45 mx=std::min(mx,points[i].x);Mx=std::max(Mx,points[i].x);46 my=std::min(my,points[i].y);My=std::max(My,points[i].y);47 }48 int lf=0, rg=std::max(Mx-mx,My-my);49 while(lf<=rg) {50 int mid=(lf+rg)>>1;51 memset(vis,0,sizeof(vis));52 if(!DFS(mid,3)) lf=mid+1;53 else rg=mid-1; 54 }55 printf("%d\n",lf);56 return 0;57 }
1 /************************************************************** 2 Problem: 1052 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:348 ms 7 Memory:1056 kb 8 ****************************************************************/ 9 10 #include11 #include 12 #include 13 template inline void readin(T &res) {14 static char ch;T flag=1;15 while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;16 res=ch-48;while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;res*=flag;17 }18 const int N = 20010;19 const int inf = 0x3f3f3f3f;20 struct Point { int x,y;}points[N];21 int n, vis[N];22 int DFS(int L,int siz) {23 int xx[2], yy[2];24 xx[0]=yy[0]=inf;xx[1]=yy[1]=-inf;25 for( int i = 1; i <= n; i++ ) if(!vis[i]) {26 xx[0]=std::min(xx[0],points[i].x);xx[1]=std::max(xx[1],points[i].x);27 yy[0]=std::min(yy[0],points[i].y);yy[1]=std::max(yy[1],points[i].y);28 }29 if(siz==1) return xx[1]-xx[0]<=L && yy[1]-yy[0]<=L;30 for( int i = 0; i <= 1; i++ ) for( int j = 0; j <= 1; j++ ) {31 for( int k = 1; k <= n; k++ ) if(!vis[k]&&std::max(abs(points[k].x-xx[i]),abs(points[k].y-yy[j]))<=L) vis[k]=siz;32 if(DFS(L,siz-1)) return 1;33 for( int k = 1; k <= n; k++ ) if(vis[k]==siz) vis[k]=0;34 }35 return 0;36 }37 int main() {38 readin(n);39 int mx=inf, my=inf, Mx=-inf, My=-inf;40 for( int i = 1; i <= n; i++ ) {41 readin(points[i].x), readin(points[i].y);42 mx=std::min(mx,points[i].x);Mx=std::max(Mx,points[i].x);43 my=std::min(my,points[i].y);My=std::max(My,points[i].y);44 }45 int lf=0, rg=std::max(Mx-mx,My-my);46 while(lf<=rg) {47 int mid=(lf+rg)>>1;48 memset(vis,0,sizeof(vis));49 if(!DFS(mid,3)) lf=mid+1;50 else rg=mid-1; 51 }52 printf("%d\n",lf);53 return 0;54 }55
为什么？因为放第三块布前不再需要枚举4个角，可以直接判断。递归便彻彻底底地少了一层。确实很有实际价值。不过此题WA了很久，就是因为偷懒ctrl+c却不考虑实际情况啊。