NOIP2017 D2T1奶酪

这题终于是正经第一题感觉了。

只需要对相交或相切的球建一条边，然后对所有与底面有交点的球连边，再对所有与顶面有交点的球连边，bfs判断上下连通性即可。

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 typedef long long ll;

 struct point

 {

     long long x,y,z;

 }p[];

 bool v[];

 double c(point a,point b)

 {

     return sqrt(1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y)+1ll*(a.z-b.z)*(a.z-b.z));

 }

 int head[],cnt;

 struct node

 {

     int to,nex;

 }e[];

 void add(int x,int y)

 {

     e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt;

 }

 queue<int>q;int n,h,r;

 bool bfs()

 {

     memset(v,,sizeof(v));

     while(!q.empty())q.pop();

     q.push();v[]=;

     while(!q.empty())

     {

         int x=q.front();q.pop();if(x==n+)return ;

         for(int i=head[x];i;i=e[i].nex)

         {

             int y=e[i].to;

             if(v[y])continue;

             q.push(y);v[y]=;

         }

     }

     return ;

 }

 int main()

 {

     //freopen("cheese.in","r",stdin);

     //freopen("cheese.out","w",stdout);

     int t;

     scanf("%d",&t);

     while(t--)

     {

         cnt=;memset(head,,sizeof(head));

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

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

         {

             scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].z);

         }

         p[].x=p[].y=p[].z=;p[n+].x=p[n+].y=;p[n+].z=h;

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

         {

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

             {

                 double dis=c(p[i],p[j]);

                 if(dis>r+r)continue;add(i,j),add(j,i);

             }

         }

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

         {

             if(p[i].z<=r&&p[i].z>=-r)add(,i);

             if(p[i].z>=h-r&&p[i].z<=h+r)add(i,n+);

         }

         if(bfs())puts("Yes");

         else puts("No");

     }

     //fclose(stdin);

     //fclose(stdout);

     return ;

 }