题目概述
有
n
n
个点，用 33 块
L×L
L
×
L
的布盖住所有点，求最小的
L
L
<script type="math/tex" id="MathJax-Element-4">L</script> 。
解题报告
这是道套路贪心假题……首先二分将求最优解问题转换为判定问题，然后我们找出盖住所有点的最小矩阵，则第一块布一定是盖在这个矩阵的四个角上。
为什么？因为最边上的点一定要盖住的，那么莫不如就贴着最边上的点盖，套路的贪心想法……
第二块布也这么盖，第三块布直接判断就行了。
示例程序
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn
=20000;
int n,x[maxn
+5],y[maxn
+5],vis[maxn
+5];
bool check(
int len,
int st
=1){
if (st
>3)
return false;
int L
=2e9,R=-L,U=L,D=-L;
for (
int i
=1;i<=n;i++)
if (!vis[i]) L=min(L,y[i]),R=max(R,y[i]),U=min(U,x[i]),D=max(D,x[i]);
if (R-L<=
len&&D-U<=
len)
return true;
for (
int i
=1;i<=n;i++) vis[i]+=y[i]-L<=
len&&x[i]-U<=
len;
if (check(
len,st
+1))
return true;
for (
int i
=1;i<=n;i++) vis[i]-=y[i]-L<=
len&&x[i]-U<=
len;
for (
int i
=1;i<=n;i++) vis[i]+=R-y[i]<=
len&&x[i]-U<=
len;
if (check(
len,st
+1))
return true;
for (
int i
=1;i<=n;i++) vis[i]-=R-y[i]<=
len&&x[i]-U<=
len;
for (
int i
=1;i<=n;i++) vis[i]+=y[i]-L<=
len&&D-x[i]<=
len;
if (check(
len,st
+1))
return true;
for (
int i
=1;i<=n;i++) vis[i]-=y[i]-L<=
len&&D-x[i]<=
len;
for (
int i
=1;i<=n;i++) vis[i]+=R-y[i]<=
len&&D-x[i]<=
len;
if (check(
len,st
+1))
return true;
for (
int i
=1;i<=n;i++) vis[i]-=R-y[i]<=
len&&D-x[i]<=
len;
return false;
}
int main(){
freopen(
"program.in",
"r",stdin);
freopen(
"program.out",
"w",stdout);
scanf(
"%d",&n);
for (
int i
=1;i<=n;i++) scanf(
"%d%d",&x[i],&y[i]);
int L
=0,R
=2e9;
for (
int mid=L+(R-L>
>1);L<=R;mid=L+(R-L>
>1))
(memset(vis
,0,sizeof(vis)),check(mid))?R=mid
-1:L=mid
+1;
return printf(
"%d\n",L)
,0;
}
