noip2017的并查集辣鸡题。
挺好想但是我把ans1和ans2放在循环外边了。修修改改很久也没改对心态很爆炸
不过后来在同学的帮助下改对了。
不过心态还是很爆炸。
#include#include #include #include #include #define ll long longusing namespace std;long long t,n,h,r,x[100010],y[100010],z[100010];int f[1010];int f1[100001],f2[100001];//分别记录与上表面相交/切的点和下表面相交/切的点double dis(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));}//距离公式int find(int x){ return x==f[x]?x:f[x]=find(f[x]);}//并查集找祖宗int main(){ cin>>t; for(int i=1;i<=t;i++){ cin>>n>>h>>r; int ans1=0,ans2=0; for(int j=1;j<=n;j++) f[j]=j; for(int j=1;j<=n;j++){ cin>>x[j]>>y[j]>>z[j]; if(z[j]+r>=h){ ans1++; f1[ans1]=j;//上表面相交/切的点被标记 } if(z[j]-r<=0){ ans2++; f2[ans2]=j;//下表面相交/切的点被标记 } for(int k=1;k<=j;k++){ if(dis(x[j],y[j],z[j],x[k],y[k],z[k])<=2*r){ int q1=find(j); int q2=find(k); if(q1!=q2) f[q1]=q2;//将两个相连的点的祖宗相连 } } } int right=0; for(int j=1;j<=ans1;j++){ for(int k=1;k<=ans2;k++){ if(find(f1[j])==find(f2[k])){ right=1;break; } }//看看所有相连的点是否能与上下表面相通 if(right==1) break; } if(right==1) cout<<"Yes"<