0pts 样例通过求调
查看原帖
0pts 样例通过求调
923364
OIerlb楼主2025/7/24 17:01
#include <bits/stdc++.h>

#define int long long

#define double long double

#define INF (int)(1e18)

#define maxn 300005

#define eps (1e-6)

using namespace std;

int n;

double r,l;

double a[3005],b[3005];

int fa[3005];

int get_fa(int x){
	
	return (x == fa[x] ? x : fa[x] = get_fa(fa[x]));
	
}

struct node{
	
	double mix,mxx,miy,mxy;
	
}ff[3005];

bool check(double x){
	
	for(int i = 1;i <= n;++ i){
		
		fa[i] = i;
		
//		ff[i].mix = ff[i].mxx = a[i];
//		
//		ff[i].miy = ff[i].mxy = b[i];
		
		ff[i].mix = a[i] - x;
		
		ff[i].mxx = a[i] + x;
		
		ff[i].miy = b[i] - x;
		
		ff[i].mxy = b[i] + x;
		
	}
	
	for(int i = 1;i <= n;++ i){
		
		for(int j = 1;j <= n;++ j){
			
			if(i == j) continue;
			
			int ii = get_fa(i),jj = get_fa(j);
			
			if(ii == jj) continue;
			
			else {
				
				fa[ii] = jj;
				
				ff[jj].mix = min(ff[jj].mix,ff[ii].mix);
				
				ff[jj].mxx = max(ff[jj].mxx,ff[ii].mxx);
				
				ff[jj].miy = min(ff[jj].miy,ff[ii].miy);
				
				ff[jj].mxy = max(ff[jj].mxy,ff[ii].mxy);
				
			}
			
		}
		
	}
	
	for(int i = 1;i <= n;++ i){
		
		int k = i;
		
		i = get_fa(i);
		
		int a1 = (ff[i].mxx > r ? 1 : 0);//右 
		
		int b1 = (ff[i].mix < 0.0 ? 1 : 0);//左 
		
		int a2 = (ff[i].mxy > l ? 1 : 0);//上 
		
		int b2 = (ff[i].miy < 0.0 ? 1 : 0);//下 
		
		if((b1 == 1 && a1 == 1) || (b1 == 1 && b2 == 1) || (a2 == 1 && b2 == 1) || (a2 == 1 && a1 == 1)) return false;
		
		i = k;
		
	}
	
	return true;
	
}

signed main(){

	ios::sync_with_stdio(0);
	
	cin.tie(0);
	
	cout.tie(0);
	
	cin >> n >> l >> r;
	
	for(int i = 1;i <= n;++ i) cin >> a[i] >> b[i];
	
	double l = 0.0,r = (double)(30000.0);
	
	while(l < r - eps){
		
		double mid = (l + r) / 2.0;
		
		if(check(mid)) l = mid;
		
		else r = mid;
		
	}
	
	cout << fixed << setprecision(2) << l << "\n";
	
	return 0;

}
/*

*/
2025/7/24 17:01
加载中...