警告后世人!!!
查看原帖
警告后世人!!!
445896
I_m_FW楼主2021/11/6 23:21

eps=1e-5不可以!!!精度达不到!!!!

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=N*2,eps=1e-4;
struct nn{
	int x,y;
	double w;
}e[N];
int n,k,p,f[1010];
struct node{
	int x,y;
}a[N];
bool cmp(nn xx,nn yy){
	return xx.w<yy.w;
}
int get(int a){
	if(f[a]==a)return a;
	return f[a]=get(f[a]);
}
bool krus(double mid){
	int res=1;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=p;i++){
		int x=get(e[i].x),y=get(e[i].y);
		double ee=e[i].w;
		if(x==y)continue;
		if(ee>mid)res++;
		f[x]=y;
	}
	if(res<k)return false;
	return true;
}
int main(){
	cin>>n>>k;
	double maxx=0.00000;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
		for(int j=1;j<=i-1;j++){
			double len;
			len=(double)sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
			e[++p].x=i;e[p].y=j;e[p].w=len;
			e[++p].y=i;e[p].x=j;e[p].w=len;
		}
	}
	sort(e+1,e+1+p,cmp);
	double l=0,r=1e5;
	while(l+1e-4<r){
		double mid=(l+r)/2;
		//cout<<mid<<' '<<l<<' '<<r<<endl;
		if(krus(mid))l=mid;
		else r=mid;
	}
	printf("%.2lf",l);
	return 0;
}```
2021/11/6 23:21
加载中...