BZOJ 1052 [HAOI2007]覆盖问题

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

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 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 template<class T>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
",lf);
56     return 0;
57 }

二分答案（760 ms 1056 kb）

 1 /**************************************************************
 2     Problem: 1052
 3     User: Doggu
 4     Language: C++
 5     Result: Accepted
 6     Time:348 ms
 7     Memory:1056 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 template<class T>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
",lf);
53     return 0;
54 }
55

二分答案（348 ms 1056 kb）

　　为什么？因为放第三块布前不再需要枚举4个角，可以直接判断。递归便彻彻底底地少了一层。确实很有实际价值。不过此题WA了很久，就是因为偷懒ctrl+c却不考虑实际情况啊。