70分求助
查看原帖
70分求助
1100788
CheeseFunction楼主2024/8/15 08:43

感觉没什么问题,就是三个点一直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;
} 

2024/8/15 08:43
加载中...