【NOIP2017】 奶酪
题目：奶酪
解题思路：
同样的，可以用dfs做，但是有没有发现，用并查集做会更加地，简单？
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100005;
int f[1005];
void init(int n)
{
for(int i=1;i<=n;i++)
f[i]=i;
}
int get(int x)
{
return f[x]=(x==f[x]?x:get(f[x]));
}
void merge(int x,int y)
{
f[get(x)]=get(y);
}
long long dis(long long x,long long y,long long z,long long x1,long long y1,long long z1)
{
return (x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1);
}
long long x[maxn],y[maxn],z[maxn];
int f1[maxn],f2[maxn];
int t;
int n,h;
long long r;
int main()
{
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>n>>h>>r;
int t1=0,t2=0;
init(n);
for(int j=1;j<=n;j++)
{
cin>>x[j]>>y[j]>>z[j];
if(z[j]+r>=h)
{
t1++;
f1[t1]=j;
}
if(z[j]-r<=0)
{
t2++;
f2[t2]=j;
}
for(int k=1;k<=j;k++)
{
if((x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k])>4*r*r)
continue;
if(dis(x[j],y[j],z[j],x[k],y[k],z[k])<=4*r*r)
{
int a1=get(j);
int a2=get(k);
if(a1!=a2)
f[a1]=a2;
}
}
}
int s=0;
for(int j=1;j<=t1;j++)
{
for(int k=1;k<=t2;k++)
{
if(get(f1[j])==get(f2[k]))
{
s=1;
break;
}
}
if(s==1)
break;
}
if(s==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}