感觉没什么问题,就是三个点一直WA,有没有大佬可以出手相救?
#include<bits/stdc++.h>
#define inf INT_MAX*2
#define int long long
using namespace std;
long long x[30000],y[30000];
long long flag[30000];
int n,bc;
bool dfs(int temp){
long long x1=inf,x2=-inf,y1=inf,y2=-inf; //定义对于树苗的最大最小x,y
for(int i=1;i<=n;i++)
if(!flag[i])
x1=min(x1,x[i]),x2=max(x2,x[i]),y1=min(y1,y[i]),y2=max(y2,y[i]);
if(max(x2-x1,y2-y1)<=bc)return true;
if(temp==3)return false;
long long demo[4][4]={0};
demo[0][0]=x1,demo[0][1]=x1+bc,demo[0][2]=y1,demo[0][3]=y1+bc;
demo[1][0]=x1,demo[1][1]=x1+bc,demo[1][2]=y2-bc,demo[1][3]=y2;
demo[2][0]=x2-bc,demo[2][1]=x2,demo[2][2]=y1,demo[2][3]=y1+bc;
demo[3][0]=x2-bc,demo[3][1]=x2,demo[3][2]=y2-bc,demo[3][3]=y2;
//定义地毯可能存在的位置
for(int i=0;i<4;i++){
int x_1,x_2,y_1,y_2;
x_1=demo[i][0],x_2=demo[i][1],y_1=demo[i][2],y_2=demo[i][3];
for(int j=1;j<=n;j++)
if(!flag[j])
if(x_1<=x[j] && x_2>=x[j] && y_1<=y[j] && y_2>=y[j])
flag[j]=temp;
if(dfs(temp+1)){
return true;
}
memset(flag,false,sizeof(flag));
}
return false;
}
bool check(int mid){
memset(flag,false,sizeof(flag));
bc=mid;
return dfs(1);
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
long long left=0,right=3e9;
while(right-left>0){
int mid=(left+right)>>1;
if(!check(mid)){
left=mid+1;
}else{
right=mid;
}
}
cout<<right<<endl;
}