题目链接
这道题貌似可以用BFS来写吧qwq。
我用的是并查集,把联通的洞合并在同一个几何中,最后只需要判断是否存在上表面和下表面有相同集合的洞即可。
但是需要注意的是还有这样的一种情况:有一个大洞贯穿了整个奶酪所以要对n=1时进行特判。
AC代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 10010
using namespace std;
struct item
{
int u;
double x;
double y;
double z;
int f;
}chs[MAXN];
bool book1[MAXN],book2[MAXN];
int f[MAXN];
int find(int k)
{
if(f[k]==k) return k;
else return f[k]=find(f[k]);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(book1,0,sizeof(book1));
memset(book2,0,sizeof(book2));
int n,h,r;
scanf("%d%d%d",&n,&h,&r);
for(int i=1;i<=n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
chs[i].u=i;
chs[i].x=x;
chs[i].y=y;
chs[i].z=z;
chs[i].f=i;
f[i]=i;
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int p=find(i);
int c=find(j);
double dis=sqrt((chs[i].x-chs[j].x)*(chs[i].x-chs[j].x)+(chs[i].y-chs[j].y)*(chs[i].y-chs[j].y)+(chs[i].z-chs[j].z)*(chs[i].z-chs[j].z));
// printf("dis=%f\n",dis);
if(dis<=2*r)
{
if(p==c) continue;
else
{
f[p]=c;
chs[p].f=c;
}
}
}
}
for(int i=1;i<=n;i++)
{
if(chs[i].z>=(h-r)&&chs[i].z<=h) book1[i]=1;
}
for(int i=1;i<=n;i++)
{
if(chs[i].z>=0&&chs[i].z<=r) book2[i]=1;
}
bool sign=0;
if(n==1)
{
if(2*r>=h&&chs[n].z-r<=0&&chs[n].z+r>=h)
{
printf("Yes\n");
continue;
}
else
{
printf("No\n");
continue;
}
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
// printf("f[%d]=%d ,find[%d]=%d,",i,find(i),j,find(j));
if(book1[i]&&book2[j]&&(find(i)==find(j))&&!sign)
{
sign=1;
// printf("i=%d,j=%d\n",i,j);
printf("Yes\n");
}
if(book1[j]&&book2[i]&&(find(i)==find(j))&&!sign)
{
sign=1;
// printf("i=%d,j=%d\n",i,j);
printf("Yes\n");
}
}
}
if(!sign) printf("No\n");
}
return 0;
}