BZOJ 1052 覆盖问题

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

首先可以确定此题满足可二分性，明显可以二分答案。所以我们只要能够在线性时间内检验即可了。

线性检测我们可以贪心解决，我们将每次还未被覆盖的点用一个最小的矩形来覆盖，然后每次选择用正方形覆盖它的四个角，总共递归三层,64种情况。所以我们枚举这64种情况，看是否能有一种能够覆盖所有的点。

这个贪心我开始没想到，现在也不会证明(理性想想是对的)，我开始想的取左下角的点(x优先)为正方形左下角wa了，然后左下角的点(y优先)为正方形左下角wa了，再最左最下的两条平行坐标轴线的交点为正方形左下角还是wa了。最后将三者综合起来，还是wa了，但是正确率高了一些。这启发我以后贪心可以综合起来，取最优解正确率会高很多。

 #include<vector>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cstdlib>

 using namespace std;

 #define inf (1<<29)

 #define maxn 20010

 int n,x[maxn],y[maxn]; bool exist[maxn];

 inline bool dfs(int L,int step,int all)

 {

     if (all == n) return true;

     if (step > ) return false;

     int up = -inf,down = inf,le = inf,ri = -inf;

     for (int i = ;i <= n;++i)

         if (!exist[i])

         {

             up = max(y[i],up),down = min(y[i],down);

             ri = max(x[i],ri),le = min(x[i],le);

         }

     int inc,nl,nr,nu,nd; vector <int> vec;

     inc = ; nl = le,nr = le+L,nu = up,nd = up-L;

     for (int i = ;i <= n;++i)

         if (!exist[i] && x[i] >= nl&&x[i] <= nr&&y[i] >= nd&&y[i] <= nu)

             ++inc,exist[i] = true,vec.push_back(i);

     if (dfs(L,step+,all+inc)) return true;

     for (int i = ;i < vec.size();++i) exist[vec[i]] = false; vec.clear();

     inc = ; nl = le,nr = le+L,nu = down+L,nd = down;

     for (int i = ;i <= n;++i)

         if (!exist[i] && x[i] >= nl&&x[i] <= nr&&y[i] >= nd&&y[i] <= nu)

             ++inc,exist[i] = true,vec.push_back(i);

     if (dfs(L,step+,all+inc)) return true;

     for (int i = ;i < vec.size();++i) exist[vec[i]] = false; vec.clear();

     inc = ; nl = ri-L,nr = ri,nu = up,nd = up-L;

     for (int i = ;i <= n;++i)

         if (!exist[i] && x[i] >= nl&&x[i] <= nr&&y[i] >= nd&&y[i] <= nu)

             ++inc,exist[i] = true,vec.push_back(i);

     if (dfs(L,step+,all+inc)) return true;

     for (int i = ;i < vec.size();++i) exist[vec[i]] = false; vec.clear();

     inc = ; nl = ri-L,nr = ri,nu = down+L,nd = down;

     for (int i = ;i <= n;++i)

         if (!exist[i] && x[i] >= nl&&x[i] <= nr&&y[i] >= nd&&y[i] <= nu)

             ++inc,exist[i] = true,vec.push_back(i);

     if (dfs(L,step+,all+inc)) return true;

     for (int i = ;i < vec.size();++i) exist[vec[i]] = false; vec.clear();

     return false;

 }

 inline bool okay(int L)

 {

     memset(exist,false,n+);

     return dfs(L,,);

 }

 int main()

 {

     freopen("1052.in","r",stdin);

     freopen("1052.out","w",stdout);

     scanf("%d",&n); for (int i = ;i <= n;++i) scanf("%d %d",&x[i],&y[i]);

     if (okay()) printf(""),exit();

     int l = ,r = inf,mid;

     while (l <= r)

     {

         mid = (l + r) >> ;

         if (okay(mid)) r = mid - ;

         else l = mid + ;

     }

     printf("%d",l);

     fclose(stdin); fclose(stdout);

     return ;

 }

秒客网