P3958 奶酪

传送门

思路：

　　模拟题。用并查集求出所有 “连通块” ，判断是否有 “连通块” 的最顶上和最下方都不小于奶酪的范围。

Code:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<cstdlib>

#include<stack>

#include<vector>

#include<queue>

#include<deque>

#include<map>

#include<set>

using namespace std;

#define lck_max(a,b) ((a)>(b)?(a):(b))

#define lck_min(a,b) ((a)<(b)?(a):(b))

#define INF 1e9+7

typedef long long LL;

const int maxn=1e3+;

LL T,n,h,r,up_cnt,down_cnt,fa[maxn];

bool flag;

struct hh

{

    LL x,y,z,up,down;

}t[maxn*maxn];

inline LL read()

{

    LL kr=,xs=;

    char ls;

    ls=getchar();

    while(!isdigit(ls))

    {

        if(!(ls^))

            kr=-;

        ls=getchar();

    }

    while(isdigit(ls))

    {

        xs=(xs<<)+(xs<<)+(ls^);

        ls=getchar();

    }

    return xs*kr;

}

inline LL find(LL u)

{

    return u==fa[u]?u:fa[u]=find(fa[u]);

}

inline double dis(LL u,LL v)

{

    return sqrt((t[u].x-t[v].x)*(t[u].x-t[v].x)+(t[u].y-t[v].y)*(t[u].y-t[v].y)+(t[u].z-t[v].z)*(t[u].z-t[v].z));

}

int main()

{

    freopen("cheese.in","r",stdin);

    freopen("cheese.out","w",stdout);

    T=read();

    while(T--)

    {

        flag=false,up_cnt=,down_cnt=;

        n=read();h=read();r=read();

        for(LL i=;i<=n;i++) fa[i]=i;

        for(LL i=;i<=n;i++)

        {

            t[i].x=read();t[i].y=read();t[i].z=read();

            if(t[i].z+r>=h) t[++up_cnt].up=i;

            if(t[i].z-r<=) t[++down_cnt].down=i;

            for(LL j=;j<i;j++)

            {

                if(dis(i,j)>*r) continue;

                LL r1=find(fa[i]),r2=find(fa[j]);

                if(r1!=r2) fa[r1]=r2;

            }

        }

        for(LL i=;i<=up_cnt;i++)

            for(LL j=;j<=down_cnt;j++)

            {

                LL r1=find(t[i].up),r2=find(t[j].down);

                if(r1==r2) {flag=true;break;}

            }

        if(!flag) printf("No\n");

        else printf("Yes\n");

    }

    fclose(stdin);

    fclose(stdout);

return ;

}