#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2010;
struct node {
	int l,r,w;
} a[N*N];
int p[N],n,m,c,x[N],y[N];
int find(int k) {
	if(p[k]!=k) return p[k]=find(p[k]);
	return p[k];
}
bool cmp(node a,node b) {
	return a.w<b.w;
}
long long kruskal() {
	for(int i=1; i<=n; i++) p[i]=i;
	long long ans=0,num=0;
	for(int i=1; i<=m; i++) {
		int pa=find(a[i].l),pb=find(a[i].r);
		if(pa!=pb) {
			p[pa]=pb;
			ans+=a[i].w;
			num++;
		}
	}
	return num==n-1?ans:-1;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>c;
	m=1;
	for(int i=1; i<=n; i++) cin>>x[i]>>y[i];
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(i==j) continue;
			int dist=((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			if(dist<c) continue;
			a[m].l=i;
			a[m].r=j;
			a[m].w=dist;
			m++;
		}
	}
	sort(a+1,a+1+m,cmp);
	cout<<kruskal();
	return 0;
}

0 条评论

目前还没有评论...