Dojnoip201708 cheese solution

subject

link

https://deeplearning.org.cn/problem/CCF-1147

Literal description

describe

There's a big piece of cheese , Its height is h, Its length and width can be considered infinite , There are many spherical cavities with the same radius in the middle of the cheese . We can set up a space coordinate system in this cheese , In the coordinate system , The bottom surface of the cheese is z = 0, The top surface of the cheese is z = h. Now? , There is a little mouse on the bottom of the cheese Jerry, It knows the coordinates of all the hollow centers in the cheese . If two cavities are tangent or intersect , be Jerry You can run from one hole to another , Specially , If a cavity is tangent to or intersects the lower surface ,Jerry You can run from the bottom of the cheese into the void ; If A void is tangent to or intersects the upper surface ,Jerry You can go from the void to the top of the cheese . On the lower surface of cheese Jerry Want to know , Without destroying the cheese , Can you use the existing cavity to run to the upper surface of the cheese ? Two points in space P1(x1,y1,z1)、P2(x2,y2,z2) The formula of distance is as follows ：

dist(P1,P2)=sqrt（(x1−x2)2+(y1−y2)2+(z1−z2)2）

This is the explanation of the following example ：

Input description

Enter the file name as cheese.in. Each input file contains multiple sets of data . The first line of the input file , Contains a positive integer T, Represents the number of data groups contained in the input file . Next is T Group data , The format of each group of data is as follows ： The first line contains three positive integers n,h and r, The two numbers are separated by a space , They stand for cheese The number of holes , The height of the cheese and the radius of the void . Next n That's ok , Each line contains three integers x、y、z, The two numbers are separated by a space , Said empty The coordinates of the center of the hole are (x,y,z).

Output description

The output file name is cheese.out. The output file contains T That's ok , They correspond to each other T The answer to group data , If in the first place i In group data ,Jerry You can do it from below The surface runs to the upper surface , The output “Yes”, If not , The output “No” （ No quotation marks ）.

Use case input 1

3
2 4 1
0 0 1
0 0 3
2 5 1
0 0 1
0 0 4
2 5 2
0 0 2
2 0 4
Use case output 1

Yes
No
Yes
Tips

Sample explanation ：

about 20% The data of ,n = 1,1 ≤ h , r ≤ 10,000, The absolute value of the coordinates does not exceed 10,000.

about 40% The data of ,1 ≤ n ≤ 8, 1 ≤ h , r ≤ 10,000, The absolute value of the coordinates does not exceed 10,000.

about 80% The data of , 1 ≤ n ≤ 1,000, 1 ≤ h , r ≤ 10,000, The absolute value of the coordinates does not exceed 10,000.

about 100% The data of ,1 ≤ n ≤ 1,000,1 ≤ h , r ≤ 1,000,000,000,T ≤ 20, The absolute value of the coordinates does not exceed 1,000,000,000.

Code implementation

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

const int maxn=1e3+10;
int t,n,h,r;
int fa[maxn],x[maxn],y[maxn],z[maxn],a[maxn],b[maxn]; 
inline int find(int x){
    
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
inline void union_(int x,int y){
    
	int fx1=find(x);
	int fy1=find(y);
	if(fx1==fy1)return;
	else fa[fx1]=fy1;
}
inline double dis(int x1,int y1,int z1,int x2,int y2,int z2){
    
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}
signed main(){
    
	scanf("%d",&t);
	while(t--){
    
		int cnt1=0,cnt2=0;
		scanf("%d%d%d",&n,&h,&r);
		for(int i=1;i<=n;i++){
    
			fa[i]=i;
			scanf("%d%d%d",&x[i],&y[i],&z[i]);
			if(z[i]-r<=0)a[++cnt1]=i;
			if(z[i]+r>=h)b[++cnt2]=i;
			for(int j=1;j<=i;j++){
    
				if(dis(x[i],y[i],z[i],x[j],y[j],z[j])<=2*r)union_(i,j);
			}
		}
		bool flag=false;
		for(int i=1;i<=cnt1;i++){
    
			for(int j=1;j<=cnt2;j++){
    
				if(find(a[i])==find(b[j])){
    
					flag=true;
					break;
				}
			}
			if(flag==true)break;
		}
		if(flag)printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}