主题是描绘现有的大奶酪。 其高度为h，其长度和宽度被认为是无限大的。 奶酪中间有很多相同半径的球形空腔。 你可以在这块奶酪里建立空间坐标系。 在坐标系中，奶酪的下面z=0，奶酪的上面z=h。
现在奶酪下面有只小老鼠gjdbl，我知道奶酪里所有空洞中心所在的坐标。 在两个腔相切或交叉的情况下，gjdbl可以从一个腔逃逸到另一个腔，特别是在一个腔与下表面相切或交叉的情况下，gjdbl可以从干酪的下表面逃逸到腔； 当空腔与上面相接或交叉时，gjdbl可以从空腔跑到奶酪的上面。
我想知道奶酪下面的gjdbl是否能在不破坏奶酪的情况下，利用现有的空洞跑到奶酪上面。
空间中两点p1(x1，y1，z1 )、p2 ) x2，y2，z2 ) )的距离公式如下：
dist(P1，P2 )=sqrt ) (x1x2)2) y1y2 )2) Z1Z2)2) )
输入格式输入格式：
每个输入文件包含多个数据。
的第一行包含正整数t，该正整数t表示输入文件中包含的数据集的数量。
接下来是t组的数据。 各组数据的格式如下。 第一行包含三个正整数n，h和r。 两个数之间由空格分开，分别表示干酪中空孔的数量、干酪的高度和空腔的半径。
以下n行表示每行包含三个整数x、y和z，两个数字之间用空格分隔，并且孔的球心坐标为(x、y和z )。
输出格式：
t行分别是对t组数据的回答，在第I组数据中，如果gjdbl从下面逃到上面，则输出Yes，如果不能跑，则输出No (都不含引号)。
输入输出样品输入样品#1:复制32410100032101000042020202020204输出样品#1:复制是否说明【输入输出样品1说明】
第一组数据可以从奶酪的截面图中看出。
第一个空洞在(0，0，0 )处与下表面相接
第二个空洞在(0，0，4 )处与上表面相接两个空洞在(0，0，2 )处相接
输出是
第二组数据可以从奶酪的截面图中看出。
两个空洞既不相交也不相接
输出No
第三组数据可以从奶酪的截面图中看出。
两个空腔相交，与上下表面相切或相交
输出是
【数据规模和承诺】
对于20%的数据，n=1，1h，r10，000，坐标绝对值小于等于10，000。
对于40%的数据，1n8，1h，r10，000，坐标的绝对值小于等于10，000。
对于80%的数据，1n1，000，1h，r10，000，坐标的绝对值小于等于10，000。
对于100%的数据，1n1，000，1h，r1，000，000，000，T20，坐标的绝对值小于等于1，000，000，000。
1 # include cstdio2# include cstring3# include cmath4# include algorithm5usingnamespacestd； 6 int T，I，j，n，op，fa[1005]，ta=0，to=0，di[1005]，gao[1005]； 7龙龙int h，r； 8 struct node 9 {10 long long int x； 11龙龙int y； 12龙龙int z； 13 ) a[1005]； 14intfind(intx ) 15 { 16if } fa [ x ]！=x(17{18fa[x]=find ) fa[x]； 19 ) 20返回fa [ x ]； 21 ) 22voidlianjie(intx，int y ) 23 ) 24x=find ) x； 25y=find(y； 26 fa[y]=x； 27 ) 28intmain(29 ) 30Scanf )、t )； 31for(I=1； i=T； I ) 32 {33 op=0； 34 to=0； 35 ta=0； 36scanf('%d%lld%lld )、n、h和r )； 37for(j=1； j=n； j ) 38{39fa(j )=j； 40scanf('%lld%lld )、a[j].x、a[j].y、a[j].z )； 41if(a(j ).z-r=0) 42 ) 43to； 44 di[to]=j； 45 ) 46if(a[j].zr=h ) 47 ) 48ta； 49 gao[ta]=j； 50 ) 51for(intk=1； k=j； k ) 52(53if ) sqrt ) (a(j ).x ) ) (a ) j ).y-a ) k ).y ).y ) ) a ) ) j ) ) j ) ) 65 56 } 57 ) j=ta； j ) 60(61for ) intk=1； k=to； k ) 62{63if}find(di[k]==find ) GaO[j] ) 65printf('yes ' )； 66 op=1； 67 break； 68}69}70if(op==1) 71 break； 72 ) 73if(op==0) 74printf ) )否)； 75if(I！=T ) 76printf('n ' )； 77 ) 78return0； 79 } *****这是一个并集，从保存的点到上下的点，找他们两个共同的爸爸，如果是一个就证明这条路相连，每次都要搜索这一点和他前面的点是否相连
转载于：https://www.cn blogs.com/rax-/p/9887940.html