链接

【NOIP2017】奶酪

写题之前就知道这是一道用并查集来解决的问题，所以脑海中一直在思考怎样才能用并查集。

第一个想法是将所有相交或相切的洞都并起来，在判断是否连通上表面与下表面。然而在代码实现的过程中，一是意识到了会有很多的集合，需要判断很多次，其次，并没有想到如何进行判断是否连通。

所以放弃了自己的第一种思路，但是因为自己太菜，一时半会儿也没想到该怎么写，所以借鉴了一位大佬的思路。

具体如下

1.在判断是否连通上表面与下表面这个问题，可以在遍历的同时找出触底和破顶的洞穴。

2.将触底和破顶这两种情况，作为两个集合的老大。随后将相交的洞穴相并，若最后这两种情况位于一个集合之中，则说明连通了上表面和下表面。

代码具体实现如下

#define ll long long
#define endl "\n"
using namespace std;
const int MAX=1e4;
struct kk{
    ll x;
    ll y;
    ll z;
}pp[MAX];//存入坐标。

int t;
ll a[MAX];

void in(ll n){
    for(int i=1;i<=n+2;i++){
        a[i]=i;
    }
}
bool dis(kk x,kk y,ll r){
    double a,b,c;
    a=(x.x-y.x)*(x.x-y.x);
    b=(x.y-y.y)*(x.y-y.y);
    c=(x.z-y.z)*(x.z-y.z);
    if(a+b+c-(4*r*r)>0) return false;//在这里犯了一个特别愚蠢的错误
    else return true; //原if里是这样的if(fabs(a+b+c-(4*r*r))>0.000001)
                      //这里忽视了一个很重要的问题，fabs是求绝对值的
                      //也就是永远都不会相交，然而我调了半个小时的bug
} //计算两个洞穴之间的距离。

ll _check(int x){
    int r=x;
    while(a[r]!=r){
        r=a[r];
    }
    return r;
}//查找集合的老大。

void _merge(ll x, ll y)
{
    int fdx,fdy;
    fdx=_check(x);
    fdy=_check(y);
    if(fdx!=fdy) a[fdx]=fdy;
}//将集合相并。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        ll n,h,r;
        cin>>n>>h>>r;
        in(n);
        for(int i=1;i<=n;i++){
            cin>>pp[i].x>>pp[i].y>>pp[i].z;
        }
            for(int i=1;i<=n;i++){
                if(pp[i].z<=r) _merge(i,n+1);//触底
                if(pp[i].z+r>=h) _merge(i,n+2);//破顶
                for(int j=i+1;j<=n;j++){
                    if(dis(pp[i],pp[j],r)){
                        _merge(i,j); //相并
                }
            }
        }
    
    if(_check(n+1)==_check(n+2)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    }
    return 0;
}