[关闭]
@ysner 2018-07-19T00:40:59.000000Z 字数 2241 阅读 1978

[HAOI2007]覆盖问题

贪心 二分


题面

最小化,使的正方形能覆盖图上个点。

解析

首先肯定要二分答案,是算不出来的。
然后构建一个覆盖所有点的最小矩形。
注意到每条边至少要一个正方形靠着。
但现在只有个正方形,意味着至少有一个正方形靠着两条边。
靠着相对的两条边?那说明这个图被这个正方形并排着覆盖。
即一定存在靠着相邻两条边(在四角)的正方形。
可以把四种情况都试一遍。
个覆盖之后又可以重复上面的步骤,以此类推。

然而我因为各种愚蠢错误了一版,如开全局变量(开局部才能保证互不影响)、打错条件与数字。。。
复杂度上限

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #define re register
  8. #define il inline
  9. #define ll long long
  10. #define max(a,b) ((a)>(b)?(a):(b))
  11. #define min(a,b) ((a)<(b)?(a):(b))
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=2e4+100;
  16. int n,x[N],y[N];
  17. bool vis[N];
  18. il ll gi()
  19. {
  20. re ll x=0,t=1;
  21. re char ch=getchar();
  22. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  23. if(ch=='-') t=-1,ch=getchar();
  24. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  25. return x*t;
  26. }
  27. il int solve(re ll l,re ll r,re ll u,re ll d,re int t,re ll L)
  28. {
  29. re bool viss[N]={};fp(i,1,n) viss[i]=vis[i];
  30. re int flag=1;
  31. fp(i,1,n) if(!vis[i]) flag=0;
  32. if(flag) return 1;
  33. else if(t>3) return 0;
  34. {
  35. re int zz=1e9,xx=1e9,yy=-1e9,ss=-1e9;
  36. fp(i,1,n) if(x[i]>=l&&y[i]>=d&&x[i]<=l+L&&y[i]<=d+L) vis[i]=1;
  37. fp(i,1,n) if(!vis[i]) zz=min(zz,x[i]),yy=max(yy,x[i]),xx=min(xx,y[i]),ss=max(ss,y[i]);
  38. if(solve(zz,yy,ss,xx,t+1,L)) return 1;
  39. fp(i,1,n) vis[i]=viss[i];
  40. }
  41. {
  42. re int zz=1e9,xx=1e9,yy=-1e9,ss=-1e9;
  43. fp(i,1,n) if(x[i]>=l&&y[i]<=u&&x[i]<=l+L&&y[i]>=u-L) vis[i]=1;
  44. fp(i,1,n) if(!vis[i]) zz=min(zz,x[i]),yy=max(yy,x[i]),xx=min(xx,y[i]),ss=max(ss,y[i]);
  45. if(solve(zz,yy,ss,xx,t+1,L)) return 1;
  46. fp(i,1,n) vis[i]=viss[i];
  47. }
  48. {
  49. re int zz=1e9,xx=1e9,yy=-1e9,ss=-1e9;
  50. fp(i,1,n) if(x[i]<=r&&y[i]>=d&&x[i]>=r-L&&y[i]<=d+L) vis[i]=1;
  51. fp(i,1,n) if(!vis[i]) zz=min(zz,x[i]),yy=max(yy,x[i]),xx=min(xx,y[i]),ss=max(ss,y[i]);
  52. if(solve(zz,yy,ss,xx,t+1,L)) return 1;
  53. fp(i,1,n) vis[i]=viss[i];
  54. }
  55. {
  56. re int zz=1e9,xx=1e9,yy=-1e9,ss=-1e9;
  57. fp(i,1,n) if(x[i]<=r&&y[i]<=u&&x[i]>=r-L&&y[i]>=u-L) vis[i]=1;
  58. fp(i,1,n) if(!vis[i]) zz=min(zz,x[i]),yy=max(yy,x[i]),xx=min(xx,y[i]),ss=max(ss,y[i]);
  59. if(solve(zz,yy,ss,xx,t+1,L)) return 1;
  60. return 0;
  61. }
  62. }
  63. int main()
  64. {
  65. n=gi();
  66. re int zz=1e9,xx=1e9,yy=-1e9,ss=-1e9;
  67. fp(i,1,n) x[i]=gi(),y[i]=gi(),zz=min(zz,x[i]),yy=max(yy,x[i]),xx=min(xx,y[i]),ss=max(ss,y[i]);
  68. re ll l=1,r=2e9,ans=1;
  69. while(l<=r)
  70. {
  71. re ll mid=l+r>>1;
  72. memset(vis,0,sizeof(vis));
  73. if(solve(zz,yy,ss,xx,1,mid)) ans=mid,r=mid-1;
  74. else l=mid+1;
  75. }
  76. printf("%lld\n",ans);
  77. return 0;
  78. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注