rt,错的点跟其他人都一样。
看到第二篇题解说
dfs里的变量一定要开局部!开全局的话死不瞑目啊!
可是不知道我的代码里哪一部分开局部,我都有清空qwq
求助:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=20005;
const int inf=100000000010;
inline int read()
{
register int x=0,f=1;
register char c=getchar();
for(;!(c>='0'&&c<='9');c=getchar())
if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+c-'0';
return x*f;
}
struct p
{
int x,y;
int ok;
}a[maxn],J[5][5];
int n;
void build(int step)
{
J[step][1].x=-inf,J[step][1].y=-inf,J[step][3].x=inf,J[step][3].y=inf;
for(register int i=1;i<=n;i++)
{
if(a[i].ok) continue;
J[step][1].x=max(J[step][1].x,a[i].x),J[step][3].x=min(J[step][3].y,a[i].x);
J[step][1].y=max(J[step][1].y,a[i].y),J[step][3].y=min(J[step][3].y,a[i].y);
}
J[step][2].x=J[step][3].x,J[step][2].y=J[step][1].y;
J[step][4].x=J[step][1].x,J[step][4].y=J[step][3].y;
}
void clear(int step)
{
for(register int i=1;i<=n;i++)
if(a[i].ok>step) a[i].ok=0;
}
bool dfs(int x,int y,int L,int step)
{
if(step==4)
return (J[step][1].x==-inf);
for(register int i=1;i<=n;i++)
if(a[i].x<=x&&a[i].y<=y&&x-a[i].x<=L&&y-a[i].y<=L&&a[i].ok==0)
a[i].ok=step;
build(step+1);
if(dfs(J[step+1][1].x,J[step+1][1].y,L,step+1)) return 1;
clear(step);
if(dfs(J[step+1][2].x+L-1,J[step+1][2].y,L,step+1)) return 1;
clear(step);
if(dfs(J[step+1][3].x+L-1,J[step+1][3].y+L-1,L,step+1)) return 1;
clear(step);
if(dfs(J[step+1][4].x,J[step+1][4].y+L-1,L,step+1)) return 1;
clear(step);
return 0;
}
bool check(int L)
{
register int ans=0;
ans+=dfs(J[1][1].x,J[1][1].y,L,1),clear(0);
ans+=dfs(J[1][2].x+L-1,J[1][2].y,L,1),clear(0);
ans+=dfs(J[1][3].x+L-1,J[1][3].y+L-1,L,1),clear(0);
ans+=dfs(J[1][4].x,J[1][4].y+L-1,L,1),clear(0);
return ans;
}
signed main()
{
n=read();
int mid,l=1,r;
J[1][1].x=-inf,J[1][1].y=-inf,J[1][3].x=inf,J[1][3].y=inf;
for(register int i=1;i<=n;i++)
{
a[i].x=read(),a[i].y=read(),a[i].ok=0;
J[1][1].x=max(J[1][1].x,a[i].x),J[1][3].x=min(J[1][3].y,a[i].x);
J[1][1].y=max(J[1][1].y,a[i].y),J[1][3].y=min(J[1][3].y,a[i].y);
}
J[1][2].x=J[1][3].x,J[1][2].y=J[1][1].y;
J[1][4].x=J[1][1].x,J[1][4].y=J[1][3].y;
r=max(J[1][1].x-J[1][3].x+1,J[1][1].y-J[1][3].y+1);
while(r>l)
{
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
// if(r%10==4&&r>100&&r<1000)
// r--;
cout<<r<<endl;
return 0;
}