并查集 50分最后5个点全部TLE
查看原帖
并查集 50分最后5个点全部TLE
590635
2021we楼主2022/2/21 16:32

十分迷惑

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int n,h,r;
struct node{
	int x,y,z;
}map[1010];
int fa[1010];

int find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}

void add(int x,int y) //x y
{
	int a=find(x);
	int b=find(y);
	if(map[a].z>map[b].z) a=b;
	fa[a]=b;
}

double dist(node p1,node p2)
{
	return sqrt(pow(p1.x-p2.x,2)+pow(p1.y-p2.y,2)+pow(p1.z-p2.z,2));
}

void prework()
{
	for(register int i=1;i<=n;i++)
		fa[i]=i;
	for(register int i=1;i<=n;i++)
	{
		for(register int j=1;j<=n;j++)
		{
			if(dist(map[i],map[j])<=r+r)
				add(i,j);
		}
	}
}

int main()
{
	int T;
	cin>>T;
	while(T!=0)
	{
		T--;
		scanf("%d%d%d",&n,&h,&r);
		for(register int i=1;i<=n;i++)
			cin>>map[i].x>>map[i].y>>map[i].z;
		prework();
		bool flag=false;
		for(register int i=1;i<=n;i++)
		{
			if(map[i].z-r<=0 && map[fa[i]].z+r>=h)
			{
				flag=true;
				break;
			}
		}
		if(flag) printf("Yes\n");
		else	 printf("No\n");
	}
	return 0;
}
2022/2/21 16:32
加载中...