linkkkk
题意：
现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪 中间有许多 半径相同 的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中， 奶酪的下表面为z=0，奶酪的上表面为z=h。
现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐 标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别 地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果 一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。
位于奶酪下表面的 Jerry 想知道，在 不破坏奶酪 的情况下，能否利用已有的空洞跑 到奶酪的上表面去?
思路：
暴力判断两个点是否相交，用并查集维护连通性，判断上表面和下表面是否相交。
代码：
// Problem: B. Weakened Common Divisor // Contest: Codeforces - Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) // URL: https://codeforces.com/contest/1025/problem/B // Memory Limit: 256 MB // Time Limit: 1500 ms // // Powered by CP Editor (https://cpeditor.org) #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> #include<map> #include<set> #include<vector> #include<queue> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b, ll p) { ll res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; #define PI acos(-1) const int maxn=5e5+100; ll n,h,r; struct node{ ll x,y,z; }a[maxn]; ll cul(node a,node b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z); } int root[maxn]; int Find(int x){ if(x!=root[x]) return root[x]=Find(root[x]); return root[x]; } int main(){ int T=read; while(T--){ n=read,h=read,r=read; rep(i,1,n){ a[i].x=read,a[i].y=read,a[i].z=read; } rep(i,1,n+2) root[i]=i; rep(i,1,n){ if((a[i].z-r)<=0){ int fx=Find(i),fy=Find(n+1); if(fx!=fy) root[fx]=fy; } if((a[i].z+r)>=h){ int fx=Find(i),fy=Find(n+2); if(fx!=fy) root[fx]=fy; } rep(j,i+1,n){ if(cul(a[i],a[j])<=(2*r)*(2*r)){ int fx=Find(i),fy=Find(j); if(fx!=fy) root[fx]=fy; } } } if(Find(n+1)==Find(n+2)) puts("Yes"); else puts("No"); } return 0; }
