全WA,玄关求调
查看原帖
全WA,玄关求调
785713
yzjznbQWQ楼主2024/9/30 21:17

rt

#include<bits/stdc++.h>

using namespace std;

#define pii pair<int,int>
const int N = 1e3+5;

inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();	
	}	
	while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
	return x*f;
} 

int n=read(),k=read(),min_n=0x3f3f3f3f,fa[N],cnt=0;
pii a[N];

int find_(int x)//查找祖先
{
	// return fa[x]=(fa[x]!=x)?find_(fa[x]):x;
    if(fa[x]==x)
        return x;
    return fa[x]=find_(fa[x]);
}

void add_(int x,int y)//合并并查集
{
	fa[find_(x)]=find_(y);
}

double dis(double x,double y,double x_,double y_)
{
	return (x-y)*(x-y)+(x_-y_)*(x_-y_);
}

int kruskal(double k)
{
	
	for(int i=1;i<=n;i++) fa[i]=i;
	cnt=0;
    for(int i=1;i<=n;i++)
	{
		int x=a[i].first,y=a[i].second;
		for(int j=1;j<=n;j++)
		{
			//if(j==i) continue;
			if(dis(x,y,a[j].first,a[j].second)<=k)
				add_(i,j);
		}
	}
    for(int i=1;i<=n;i++)
        if(find_(i)==i) cnt++;
	if(cnt<k)
        return false;
    return true;
    // return cnt;
}

int main(){
	for(int i=1;i<=n;i++) a[i].first=read(),a[i].second=read();
	double l=0.0,r=2e9;
	double mid;
    //int cnt=0;
	while(r-l>1e-4)//二分平方
	{//min_n=min_n>mid?mid:min_n;
        //cnt++;
		mid=(l+r)/2.0;
        //int yuan1123ppppp=kruskal(mid);
		// if(cnt<k) 
        //     r=mid;
		// else 
        //     l=mid;
        // cout<<" "<<r<<" "<<l<<endl;
        // if(cnt==40) break;
        // if(l==r) cout<<1;
         if(!kruskal(mid))
            r=mid;
        else
            l=mid;
	}
	printf("%.2lf\n",sqrt(l));
	return 0;
}
2024/9/30 21:17
加载中...