【NOIP2017】奶酪

现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的
奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系。
在坐标系中， 奶酪的下表面为z = 0，奶酪的上表面为z = h。

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。
如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，
特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；
如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑到奶酪的上表面去?

NOIP的一道水题
我居然做了一个小时？？？
可能是今天脑子不好用吧

显然每次\(\Theta(n^2)\)枚举两两空洞，看是否联通
用并查集维护即可

放一下今晚的傻逼错误集锦：
1、坐标不开long long，等着退役吧
2、计算距离的时候z轴写成了(double)(z1z2)-(double)(z1z2)，为此还拆开写才检查出来，等着退役吧
3、查询的时候用的fa，而不是find，等着退役吧
4、第一次打的时候是从0~n+1，看是否都联通了。然而有可能会有独立的空洞，只需要看上下表面是否联通即可，等着退役吧

蠢

#include<bits/stdc++.h>
#define ll long long
#define N 1005
using namespace std;

ll T,n,r,h;

struct Node
{
    ll x,y,z;
}a[N];

ll fa[N];

ll find(ll x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

double dis(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2)
{
    double d1=(double)(x1-x2)*(double)(x1-x2);
    double d2=(double)(y1-y2)*(double)(y1-y2);
    double d3=(double)(z1-z2)*(double)(z1-z2);
    return sqrt(d1+d2+d3);
}

void Merge(ll x,ll y)
{
    int fx=find(x),fy=find(y);
    if(fx==fy) return;
//  cout<<"Merge : "<<x<<" "<<y<<endl;
    fa[fx]=fy;
}

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

int main()
{
    read(T);
    while(T--)
    {
        read(n);read(h);read(r);
        for(register int i=0;i<=n+1;++i) fa[i]=i;
        for(register int i=1;i<=n;++i)
        {
            read(a[i].x);
            read(a[i].y);
            read(a[i].z);
        }
        for(register int i=1;i<=n;++i)
        {
            if(a[i].z<=r) Merge(0,i);
            if(a[i].z>=h-r) Merge(i,n+1);
            for(register int j=1;j<i;++j)
            {
//              cout<<"dis: "<<i<<" "<<j<<" "<<dis(a[i].x,a[i].y,a[i].z,a[j].x,a[j].y,a[j].z)<<endl;
                if(dis(a[i].x,a[i].y,a[i].z,a[j].x,a[j].y,a[j].z)<=(double)r*2.0) Merge(i,j);
            }
        }
        if(find(0)!=find(n+1)) puts("No");
        else puts("Yes");
    }
    return 0;
}