pypy3 解法, 执行用时: 91ms, 内存消耗: 22920K, 提交时间: 2023-04-29 16:05:24

def dist(x1,y1,x2,y2):
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)
n,d=map(int,input().split())
d=d*d
fa=[i for i in range(1010)]
cnt=0
def find(x):
    if x==fa[x]:
        return x
    else:
        fa[x]=find(fa[x])
    return fa[x]
def merge(x,y):
    global cnt
    fx=find(x)
    fy=find(y)
    if fx!=fy :
        cnt+=1
        fa[fx]=fy
a=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append((x,y))
for i in range(n):
    for j in range(i+1,n):
        if dist(a[i][0],a[i][1],a[j][0],a[j][1])<=d:
            merge(i,j)
print(n-cnt)

C(clang11) 解法, 执行用时: 3ms, 内存消耗: 372K, 提交时间: 2021-01-01 15:31:20

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
int main(){int n,d,i,j,a,b;
    int s[1003][2],q[1003];
int v=1;
scanf("%d%d",&n,&d);
for(i=0;i<n;i++)
    scanf("%d%d",&s[i][0],&s[i][1]);
if(d){
for(i=0;i<n;i++)
        {q[i]=v;
            for(j=0;j<n;j++)
{
    if(i!=j&&(s[i][0]-s[j][0])*(s[i][0]-s[j][0])+(s[i][1]-s[j][1])*(s[i][1]-s[j][1])<=d*d){if(q[j]&&q[j]<q[i]){q[i]=q[j];v-=1;
    }else q[j]=q[i];}

}v++;}

printf("%d",v-1);
}
else printf("%d",n);

}

C++ 解法, 执行用时: 4ms, 内存消耗: 412K, 提交时间: 2021-12-23 23:05:41

#include<bits/stdc++.h>

using namespace std;

int n,d,ans;
int fa[1005],x[1005],y[1005];
int f(int s){
	if(fa[s]!=s)
		return f(fa[s]);
	return s;
}
int main(){
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		for(int j=1;j<i;j++){
			if((y[j]-y[i])*(y[j]-y[i])+(x[j]-x[i])*(x[j]-x[i])<=d*d)
				fa[f(i)]=f(j);
		}
	}
	for(int i=1;i<=n;i++){
		if(fa[i]==i){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}