大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
标题效果：特定n点。涵盖所有的点与同方三面。斧头要求方垂直边界，最小平方的需求方长值
最大值至少。答案是很明显的二分法
但验证是一个问题
考虑仅仅有三个正方形，故用一个最小矩形覆盖这三个正方形时至少有一个在角上 若有四个正方形该结论不成立
于是我们採用DFS的方式 每次用一个最小的矩形覆盖全部的点，枚举矩形的四个角 将正方形填进去
因为最大深度是3，所以时间上全然能够承受
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 20100
using namespace std;
struct abcd{
int x,y;
}points[M];
int n,v[M];
int stack[M],top;
bool DFS(int L,int dpt)
{
int i,j,bottom=top;
int minx=0x3f3f3f3f,maxx=0xefefefef;
int miny=0x3f3f3f3f,maxy=0xefefefef;
if(top==n)
return true;
if(dpt==3)
return false;
for(i=1;i<=n;i++)
if(!v[i])
{
minx=min(minx,points[i].x);
maxx=max(maxx,points[i].x);
miny=min(miny,points[i].y);
maxy=max(maxy,points[i].y);
}
int dx[]={minx,minx,maxx-L,maxx-L};
int dy[]={miny,maxy-L,miny,maxy-L};
for(j=0;j<4;j++)
{
for(i=1;i<=n;i++)
if(!v[i])
if(points[i].x>=dx[j]&&points[i].x<=dx[j]+L)
if(points[i].y>=dy[j]&&points[i].y<=dy[j]+L)
v[i]=1,stack[++top]=i;
bool flag=DFS(L,dpt+1);
while(top!=bottom)
v[stack[top--]]=0;
if(flag)
return true;
}
return false;
}
int Bisection()
{
int l=0,r=0x3f3f3f3f;
while(l+1<r)
{
int mid=l+r>>1;
if( DFS(mid,0) )
r=mid;
else
l=mid;
}
if( DFS(l,0) )
return l;
return r;
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n;i++)
scanf("%d%d",&points[i].x,&points[i].y);
cout<<Bisection()<<endl;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117596.html原文链接：https://javaforall.net
