本题是NOIP2017 Day2 T1.
这题我居然想了半天..法一：考虑并查集做法。我们想，如果一个相交或者相切就能互相移动，那我们不如把相交或者相切的合并，最后遍历一下下表面的所有点看看能不能跑上去就OK了。Code：#include#include #include #include #define int long long#define maxn 100001using namespace std;struct Edge{ int x,y,z;}edge[maxn];int fa[maxn],n,h,r,up,low,p1[maxn],p2[maxn];inline void clear(){ for(int i=1;i<=n;i++){ fa[i]=i; } up=0; low=0; memset(p1,0,sizeof(p1)); memset(p2,0,sizeof(p2));}inline double calc(int x_1,int x_2,int y_1,int y_2,int z_1,int z_2){ if(sqrt(((x_1-x_2)*(x_1-x_2))+((y_1-y_2)*(y_1-y_2))+((z_1-z_2)*(z_1-z_2)))<=2*r) return 1; else return 0;}int find(int x){ if(fa[x]==x) return x; else return fa[x]=find(fa[x]);}inline void merge(int x,int y){ int xx=find(x); int yy=find(y); if(xx!=yy) fa[xx]=yy;// return 1;}main(){ int T; cin>>T; while(T--){ cin>>n>>h>>r; clear(); for(int i=1;i<=n;i++){ cin>>edge[i].x>>edge[i].y>>edge[i].z; if(edge[i].z+r>=h){ up++; p1[up]=i; } if(edge[i].z-r<=0){ low++; p2[low]=i; } for(int j=1;j<=i;j++){ if(calc(edge[i].x,edge[j].x,edge[i].y,edge[j].y,edge[i].z,edge[j].z)){ merge(i,j); } } } int ans=0; for(int i=1;i<=up;i++){ for(int j=1;j<=low;j++){ if(find(p1[i])==find(p2[j])){ ans=1; break; } } } if(ans==1) cout<<"Yes"<
法二：考虑图论做法。
直接建图然后跑个spfa，解决。Code请自己写。