并查集只有60蒟蒻妹子快要哭了
查看原帖
并查集只有60蒟蒻妹子快要哭了
134651
爱心社长楼主2019/7/8 15:36
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
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-'0';
		c=getchar();
	}
	return x*f;
}const int maxn=1003; 
int t,n,h,r,x[maxn],y[maxn],z[maxn],fa[maxn],cxia,cshang,xia[maxn],shang[maxn];

int ask(int x)
{
	if(fa[x]==x) return x;
	else return fa[x]=ask(fa[x]);
}
void bing(int x,int y)
{
	fa[y]=fa[x];
 } 
 double dis(int i,int j)
 {
 	double a=(x[i]-x[j])*(x[i]-x[j]);
 	double b=(y[i]-y[j])*(y[i]-y[j]);
 	double c=(z[i]-z[j])*(z[i]-z[j]);
 	return sqrt(a+b+c);
 }
int main()
{
	t=read();
	while(t--)
	{
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		memset(z,0,sizeof(z));
		memset(fa,0,sizeof(fa));
		memset(xia,0,sizeof(xia));
		memset(shang,0,sizeof(shang));
		cxia=cshang=0;
		n=read();h=read();r=read();
		for(int i=1;i<=n;++i)
		{
			x[i]=read();y[i]=read();
			z[i]=read();fa[i]=i;
			if((max(z[i],0)-min(z[i],0))<=r)
			{
				cxia++;
				xia[cxia]=i;
			}
			if((max(z[i],h)-min(z[i],h))<=r)
			{
				cshang++;
				shang[cshang]=i;
			}
			
			}if(cxia==0 || cshang==0)
			{
				cout<<"No"<<endl;
				continue;
			}
		for(int i=1;i<=n;++i)
		{
			for(int j=i+1;j<=n;++j)
			{
				int a,b;
				if(z[i]>z[j]) a=i,b=j;
				else a=j,b=i;
				if(dis(a,b)<=2*r) bing(a,b);
			}
		}
		int f=0;
		for(int i=1;i<=cxia;++i)
		{
			for(int j=1;j<=cshang;++j)
			{
				int groundd=xia[i],skyy=shang[j];
				if(ask(groundd)==ask(skyy))
				{
					cout<<"Yes"<<endl;	
					f=1;
					break;
				}
				
			}
			if(f) break;
		}
		if(!f) cout<<"No"<<endl;
	}
}

2019/7/8 15:36
加载中...