洛咕题解 P3958奶酪[并查集]

  • A+
所属分类:代码笔记 信息技术

n很小,考虑暴力

直接每读入一个新点就计算他与已经读入的每个点的距离

用并查集维护球之间的相连关系

若dis<=2r则合并两个球

注意特判存一下与上下表面相连的球

最后枚举与上下表面相连的球的两两组合, 若其中有一对在同一集合内则Yes

  1. #include<cstdio>
  2. #define re register
  3. #define in inline
  4. #define int long long
  5. inline int read()
  6. {
  7.     int s=0,b=1;
  8.     char ch;
  9.     do{
  10.         ch=getchar();
  11.         if(ch=='-') b=-1;
  12.     }while(ch<'0' || ch>'9');
  13.     while(ch>='0' && ch<='9')
  14.     {
  15.         s=s*10+ch-'0';
  16.         ch=getchar();
  17.     }
  18.     return b*s;
  19. }//快读是不可能出锅的
  20. in int dis(int x1,int y1,int z1,int x2,int y2,int z2)
  21. {
  22.     return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2);
  23.     //dis的平方
  24. }
  25. int T,n,h,r;
  26. int f[1100];
  27. struct node{
  28.     int x,y,z;
  29. }a[1100];
  30. int up[1100],down[1100],cntu,cntd;
  31. //up,down分别存储与上表面,下表面相连的点的序号
  32. int find(int x)
  33. {
  34.     if(x!=f[x]) f[x]=find(f[x]);
  35.     return f[x];
  36. }
  37. in void u(int r1,int r2)
  38. {
  39.     f[r1]=r2;
  40. }
  41. signed main()
  42. {
  43.     T=read();
  44.     for(re int _=1;_<=T;++_)
  45.     {
  46.         n=read();
  47.         h=read();
  48.         r=read();
  49.         for(re int i=1;i<=n;++i) f[i]=i;
  50.         cntu=0,cntd=0;
  51.         for(re int i=1;i<=n;++i)
  52.         {
  53.             a[i].x=read();
  54.             a[i].y=read();
  55.             a[i].z=read();
  56.             for(int j=1;j<=i;++j)//注意自己和自己是联通的,j可以等于i
  57.             {
  58.                 int t=dis(a[i].x,a[i].y,a[i].z,a[j].x,a[j].y,a[j].z);
  59.                 if(t<=4*r*r){//注意dis是距离的平方,省去了sqrt
  60.                     int r1=find(i);
  61.                     int r2=find(j);
  62.                     if(r1!=r2) u(r1,r2);
  63.                 }
  64.             }
  65.             if(a[i].z<=r) down[++cntd]=i;
  66.             if(a[i].z>=h-r) up[++cntu]=i;
  67.         }
  68.         int flag=1;
  69.         for(re int i=1;i<=cntd;++i)
  70.         {
  71.             for(re int j=1;j<=cntu;++j)
  72.             {
  73.                 int r1=find(down[i]),r2=find(up[j]);
  74.                 if(r1==r2){
  75.                     printf("Yes\n");
  76.                     flag=0;
  77.                     break;
  78.                 }
  79.             }
  80.             if(!flag) break;//注意一旦找到可行解就要完全break出双层循环, 不然若有多解就会输出多个Yes
  81.         }
  82.         if(flag) printf("No\n");
  83.     }
  84.     return 0;
  85. }
xcc

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: