90分求助
查看原帖
90分求助
66263
Jack_cjj楼主2021/9/25 18:05
#include<iostream>
#include<cstdio>
#include<cmath>
int fa[200010];
int n;
double minup[200010];
double maxdown[200010];
double minleft[200010];
double maxright[200010];
int x[200010];
int y[200010];
int ok;
int row,line;
int t;
int rr;
int dis[6050][6050];
using namespace std;
int findzx(int k)
{
	if(fa[k]==k) return k;
	fa[k]=findzx(fa[k]);
	return fa[k];
}
double mymin(double x,double y)
{
	if(x<y) return x;
	else return y;
}
double mymax(double x,double y)
{
	if(x>y) return x;
	else return y;
}
int is(int x,double r)
{
	if(x<=4*r*r) return true;
	else return false;
}
int pd(double r)
{
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		minup[i]=y[i]-r;
		minleft[i]=x[i]-r;
		maxdown[i]=y[i]+r;
		maxright[i]=x[i]+r;
	}
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			{
				if(is(dis[i][j],r)==true)
				{
					int a=findzx(i);
					int b=findzx(j);
					if(a!=b)
					{
						a=findzx(a);
						b=findzx(b);
						fa[findzx(b)]=findzx(a);
						minup[a]=mymin(minup[a],minup[b]);
						minleft[a]=mymin(minleft[a],minleft[b]);
						maxdown[a]=mymax(maxdown[a],maxdown[b]);
						maxright[a]=mymax(maxright[a],maxright[b]);
					}
				}
			}
	for(int i=1;i<=n;i++)
		{
			if(minup[i]<1&&minleft[i]<1) return 0;
			if(minup[i]==1&&minleft[i]==1) return 0;
			if(maxdown[i]>line&&maxright[i]>row) return 0;
			if(maxdown[i]==line&&maxright[i]==row) return 0;
		}
	return 1;
}
int main()
{
	scanf("%d %d %d",&n,&row,&line);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&x[i],&y[i]);
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			dis[i][j]=dis[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
	double l=0;
	double r=max(row,line);
	double mid=0;
	for(int i=1;i<=60;i++)
	{
		//printf("%.2f %.2f\n",l,r);
		mid=(l+r)/2;
		if(pd(mid)==0) r=mid;
		else l=mid;				
	}
	printf("%.2lf\n",l);
	return 0;
}
2021/9/25 18:05
加载中...