P3958 NOIP2017 奶酪洛谷 - 华师一附中OI组

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define ull unsigned long long
using namespace std;
int t,n,tot;
int head[1010];
bool vis[1010];
long long h,r;
struct Node
{
long long x,y,z;
} p[1010];
ull get_dis(const Node &a,const Node &b)
{
return (ull)((a.x-b.x)*(a.x-b.x))+(ull)((a.y-b.y)*(a.y-b.y))+(ull)((a.z-b.z)*(a.z-b.z));
}
struct Map
{
int r,next;
} line[1001010];
void add(int x,int y)
{
tot++;
line[tot].r=y;
line[tot].next=head[x];
head[x]=tot;
}
void dfs(int x)
{
vis[x]=true;
for(int i=head[x]; i; i=line[i].next)
if(!vis[line[i].r])
dfs(line[i].r);
}
inline int read()
{
int x=0;
bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f?-x:x;
}
int main()
{
t=read();
while(t--)
{
tot=0;
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
n=read(),h=read(),r=read();
for(int i=1; i<=n; i++)
{
p[i].x=read(),p[i].y=read(),p[i].z=read();
if(p[i].z-r<=0)
add(0,i);
if(p[i].z+r>=h)
add(i,n+1);
}
for(register int i=1; i<=n; i++)
for(register int j=i+1; j<=n; j++)
if(get_dis(p[i],p[j])<=(ull)((r+r)*(r+r)))
add(i,j),add(j,i);
dfs(0);
if(vis[n+1])
puts("Yes");
else puts("No");
}
return 0;
}

复制代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
long long t,n,h,r,a[1003][4]= {0};
int lian[1003][1003]= {0},ru[1003]= {0},e=0,book[1003]= {0},la=0;
void dfs(int ha)
{
if(e)
return;
for(int i=1; i<=lian[ha][0]; i++)
{
if(lian[ha][i]==2500)
{
e=1;
return;
}
else
{
if(e)
return;
if(book[lian[ha][i]]==0)
{
book[lian[ha][i]]=1;
dfs(lian[ha][i]);
}
}
}
}
int main()
{
scanf("%lld",&t);
while(t--)
{
memset(book,0,sizeof(book));
memset(lian,0,sizeof(lian));
memset(ru,0,sizeof(ru));
memset(a,0,sizeof(a));
e=0,la=0;
scanf("%lld%lld%lld",&n,&h,&r);
for(long long i=1; i<=n; i++)
{
scanf("%lld%lld%lld",&a[i][1],&a[i][2],&a[i][3]);
if(abs(a[i][3])<=r&&abs(a[i][3])>=h-r)
la=1;
if(abs(a[i][3])<=r)
{
ru[0]++;
ru[ru[0]]=i;
}
if(abs(a[i][3])>=h-r)
{
lian[i][0]++;
lian[i][lian[i][0]]=2500;
e=1;
}
for(long long j=i-1; j>=1; j--)
{
if(sqrt((a[i][1]-a[j][1])*(a[i][1]-a[j][1])+(a[i][2]-a[j][2])*(a[i][2]-a[j][2])+(a[i][3]-a[j][3])*(a[i][3]-a[j][3]))<=(2*r))
{
lian[i][0]++;
lian[i][lian[i][0]]=j;
lian[j][0]++;
lian[j][lian[j][0]]=i;
}
}
}
if(la==1)
{
printf("Yes\n");
continue;
}
if(e==0||ru[0]==0)
{
printf("No\n");
continue;
}
e=0;
for(int i=1; i<=ru[0]; i++)
{
book[ru[i]]=1;
dfs(ru[i]);
if(e)
break;
}
if(e)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}

复制代码

#include<cstdio>
#include<algorithm>
using namespace std;
int f[1001+1][1001+1];
int t,n,h,r;
int x[1001],y[1001],z[1001];
const int INF=999999999;
struct node
{
int x;
int y;
int z;
}dong[1001];
int cmp(node a,node b)
{
if(a.z<b.z)
{
return 1;
}
else
{
return 0;
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&h,&r);
for(int i=1;i<=n;i++)
{
dong[i].x=dong[i].y=dong[i].z;
}
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&dong[i].x,&dong[i].y,&dong[i].z);
}
sort(dong+1,dong+1+n,cmp);
if(dong[1].z-r>0||dong[n].z+r<h)
{
printf("no\n");
continue;
}
for(int i=0;i<=n+1;i++)
{
for(int j=0;j<=n+1;j++)
{
if(i==j)
{
f[i][j]=0;
}
else
{
f[i][j]=INF;
}
}
}
//printf("%d ",f[0][n+1]);
for(int i=1;i<=n;i++)
{
if(dong[i].z-r<=0)
{
f[0][i]=1;
f[i][0]=1;
}
if(dong[i].z+r>=h)
{
f[n+1][i]=1;
f[i][n+1]=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(r*2*2*r>=(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i])+(z[j]-z[i])*(z[j]-z[i]))
{
f[i][j]=f[j][i]=(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i])+(z[j]-z[i])*(z[j]-z[i]);
}
}
}
//floyd大法好
for(int k=0;k<=n+1;k++)
{
for(int i=0;i<=n+1;i++)
{
for(int j=0;j<=n+1;j++)
{
if(f[i][j]>f[i][k]+f[k][j])
{
f[i][j]=f[i][k]+f[k][j];
}
}
}
}
if(f[0][n+1]>=INF)
{
printf("No\n");
}
else
{
printf("Yes\n");
}
}
return 0;
}

复制代码

#include<iostream>
#include<cmath>
using namespace std;
int t,par[1001];
int n,h,f1[1001],f2[1001],n1,n2;
bool b;
typedef long long ll;
ll r;
struct hole
{
ll x,y,z;
}a[1010];
int find(int x)
{
if (par[par[x]]!=par[x]) par[x]=par[par[x]];
return par[x];
}
double dis(ll x,ll y,ll z,ll x1,ll y1,ll z1)
{
return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1));
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>h>>r;
b=true;
n1=n2=0;
for(int i=1;i<=n;i++)par[i]=i;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y>>a[i].z;
if(a[i].z+r>=h)f1[++n1]=i;
if(a[i].z-r<=0)f2[++n2]=i;
for(int j=1;j<=i;j++)
if(dis(a[i].x,a[i].y,a[i].z,a[j].x,a[j].y,a[j].z)<=2*r)
{
int a1=find(i);
int a2=find(j);
if (a1!=a2)par[a1]=a2;
}
}
for(int i=1;i<=n1&&b;i++)
for(int j=1;j<=n2&&b;j++)
if(find(f1[i])==find(f2[j]))b=false;
if(!b)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}

复制代码

#include <cstdio>
long long top[1001],bottom[1001],count1,count2,x[1001],y[1001],z[1001],father[1001];
long long n,h,r;
int getfather(int x)
{
if(x==father[x])
return x;
return father[x]=getfather(father[x]);
}
bool judge(int i,int j)
{
long long dis=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]);
long long d=4*r*r;
if(dis<=d)
return 1;
return 0;
}
int main()
{
int t;
scanf("%d",&t);
for(int o=1;o<=t;o++)
{
scanf("%lld%lld%lld",&n,&h,&r);
count1=count2=0;
for(int i=1;i<=n;i++)
top[i]=bottom[i]=0;
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
if(z[i]<=r)
bottom[++count1]=i;
if(z[i]>=h-r)
top[++count2]=i;
for(int j=1;j<=i;j++)
if(judge(i,j) && getfather(i)!=getfather(j))
father[getfather(i)]=getfather(j);
}
int flag=0;
for(int i=1;i<=count1;i++)
{
for(int j=1;j<=count2;j++)
if(getfather(bottom[i])==getfather(top[j]))
{
flag=1;
break;
}
if(flag)
break;
}
if(flag)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}

复制代码

#include<iostream>
#include<cmath>
using namespace std;
const int mx=101000;
int t,n,par[mx];
double r;
long long x[mx],y[mx],z[mx],h;
int i,j,k;
int sunder,shead,under_[mx],head_[mx];
int getpar(int a)
{
if (a!=par[a])
par[a]=getpar(par[a]);
return par[a];
}
int main()
{
cin>>t;
while (t--)
{
cin>>n>>h>>r;
for (i=1;i<=n;i++) par[i]=i;
shead=0,sunder=0;
for (i=1;i<=n;i++)
{
cin>>x[i]>>y[i]>>z[i];
if (z[i]+r>=h)///与顶上连接
{
shead++;
head_[shead]=i;
}
if (z[i]-r<=0)
{
sunder++;
under_[sunder]=i;
}
for (j=1;j<=i;j++)
{
if (sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]))<=2*r)
if (getpar(i)!=getpar(j))
par[getpar(i)]=getpar(j);
}
}
bool bb=false;
for (i=1;i<=shead && !bb;i++)
for (j=1;j<=sunder && !bb;j++)
if (getpar(head_[i])==getpar(under_[j]))
bb=true;
if (bb) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}

复制代码