求助dalao 30Pts,玄关
查看原帖
求助dalao 30Pts,玄关
867875
niveKmAI楼主2024/7/25 16:44
#include<bits/stdc++.h>
using namespace std;
int x[3005];
int y[3005];
int fa[3005];

int n,rr,ll;
double eps=1e-4;
int find(int x) {
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void get(int x,int y) {
	int a=find(x);
	int b=find(y);
	if(a!=b) {
		fa[x]=b;
	}
}
double dist(int a,int b) {
	return (pow(x[a]-x[b],2))+(pow(y[a]-y[b],2));
}
bool check(double asp) {
//	memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++){
    	fa[i]=i;
	} 
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=i; j++){
		    if(asp*asp*4>dist(i,j)) {
				get(i,j);
			}
			if(find(i)==find(j)) {
				if((x[j]+asp>rr&&y[i]+asp>ll)||(x[j]-asp<1&&x[i]+asp>rr)||(x[i]-asp<1&&x[j]+asp>rr)||(x[i]+asp>rr&&y[j]+asp>ll)) {
					return 0;
				}
				if((y[i]-asp<1&&y[j]+asp>ll)||(y[j]-asp<1&&y[i]+asp>ll)||(x[i]-asp<1&&y[j]-asp<1)||(x[j]-asp<1&&y[i]-asp<1)) {
					return 0; 
				}
			}

		}
	}
	return 1;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>rr>>ll;
	for(int i=1; i<=n; i++) {
		fa[i]=i;
	}
	for(int i=1; i<=n; i++) {
		cin>>x[i]>>y[i];
	}
	double l=0;
	double r=min(rr,ll);
	double ans=0;
	while(fabs(l-r)>eps) {
		double mid=(l+r)/2;
		if(check(mid)==1) {
			l=mid;
			ans=max(ans,mid);
		} else {
			r=mid;
		}
	}
	printf("%.2lf\n",ans);
	return 0;
}
2024/7/25 16:44
加载中...