10pts求助dalao,4TLE,5WA,玄关
查看原帖
10pts求助dalao,4TLE,5WA,玄关
867875
niveKmAI楼主2024/7/23 21:19
#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(int asp) {
	bool su=1;
	for(int i=1; i<=n; i++){
		if(asp*asp*4>(pow)(1-x[i],2)+(pow(1-y[i],2))){
			su=0;
			break;
		}
	    else if(asp*asp*4>(pow)(rr-x[i],2)+(pow(ll-y[i],2))){
	    	su=0;
	    	break;
		}
	}
	if(su==0){
		return su;
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(i==j||find(i)==find(j)) {
				continue;
			}
			if(asp*asp*4>dist(i,j)) {
				get(i,j);
			}
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=i+1; j<=n; j++){
			if(find(i)==find(j)&&y[i]-asp<1&&y[j]+asp>ll){
				su=0;
				break;
			}
			else if(find(i)==find(j)&&x[i]-asp<1&&x[j]+asp>rr){
				su=0;
				break;
			}
			else if(find(i)==find(j)&&x[i]+asp>rr&&y[j]+asp>ll){
				su=0;
				break;
			}
			else if(find(i)==find(j)&&x[i]-asp<1&&y[j]-asp<1){
				su=0;
				break;
			}
		}
	} 
	return su;
}
signed main() {
	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);
			//cout<<ans<<"\n";
		} 
		else {
			r=mid;
		}
	}
	printf("%.2lf\n",ans);
	return 0;
}
2024/7/23 21:19
加载中...