大佬们救救40分dfs吧,救救孩子!!!!!!!!
查看原帖
大佬们救救40分dfs吧,救救孩子!!!!!!!!
388040
狂三老公楼主2020/11/7 09:39

//只有40分,不知为何

//只有40分,大佬救救孩子

#include<bits/stdc++.h>

using namespace std;

bool kk[52133]={0}; //记录空洞是否被访问过

int m,r,h,n;

struct node

{

int x,y,z;

};

bool pd[52133]={0},pd2[52133]={0},pd3=0;

node q[52133];

int pp(node a,node b)

{

double f=sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)+pow(a.z-b.z,2))	;
if(f<=2*r) return 1;
return 0;

}

void dfs(int a,int kkk)

//kkk记录前驱。如果这个空洞所在空洞链(球环)之前已经出现过下上底面相切了,那么它也可以通过空洞链或环达到下上底面。

{

if(pd3) return ;
   kk[a]=1;
if(q[a].z+r>=h && q[a].z-r<=h)
     pd[a]=1;
else pd[a]=pd[kkk];
if(q[a].z-r<=0 && q[a].z+r>=0)
	pd2[a]=1;
else pd2[a]=pd2[kkk];
if(pd[a] && pd2[a])

{

 pd3=1;
 return ;                       //记录是否找到满足题意的空洞链 

}

for(int i=a+1;i<=m;i++)
if(pp(q[a],q[i]) && (!kk[i])) 	//如果该空洞已经被访问了,就没必要再进了。因为进入该节点也找不到,否则在之前就已经return了
	 dfs(i,a);                  //访问该空洞链的下一个空洞 
else if(!kk[i] && a==1)         //或者访问另一个不相交空洞链的任意空洞,从而在后面的循环中访问该不相交空洞链所有空洞 
     dfs(i,i);

}

int main()

{

int aa[52133]={0};

scanf("%d",&n);

for(int j=1;j<=n;j++)

{

scanf("%d%d%d",&m,&h,&r);

for(int i=1;i<=m;i++)

scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);

dfs(1,1);

if(pd3) aa[j]=1;

pd3=0;

for(int i=1;i<=m;i++)

{

kk[i]=0;
pd[i]=0;
pd2[i]=0; 

}

}

for(int i=1;i<n;i++)

if(aa[i]) printf("Yes\n");

else printf("No\n");

if(aa[n]) printf("Yes");

else printf("No");

return 0;

} 
2020/11/7 09:39
加载中...