赞
踩
在一个三维空间内有一块长方体奶酪,下表面z=0,高度为h,长宽无限,其中有一些可以通过的空洞,如果两个洞相交或相切,就可以从一个空洞跑到另一个空洞。给定h和每个空洞的球心坐标和半径,问能否从下表面跑到上表面。
首先要明白对于两个球体A,B如果AB的球心距离小于等于两半径和,两球相切或相交。然后,维护一个并查集,建立一个超级起点z=0和超级终点z=h,如果两个球连通,就将它们并起来,如果与下表面相切,就与超级起点并起来,与上表面相切,就与超级终点并起来。最后查看起点与终点是否在同一个并查集内即可。
- #include <cstdio>
- #include <iostream>
- #include <cmath>
- #define ll long long
- using namespace std;
- ll T,n;
- double h,r,low,high;
- int f[1010];
- struct ball {
- double x,y,z;
- }s[1010];
- double dist(ball a,ball b) {
- double x=a.x-b.x,y=a.y-b.y,z=a.z-b.z;
- return sqrt(x*x+y*y+z*z);
- }
- int getf(int x) {
- if (f[x]==x) return x;
- return f[x]=getf(f[x]);
- }
- void Union(int x,int y) {
- x=getf(x);
- y=getf(y);
- if (x!=y) f[y]=f[x];
- }
- int main() {
- scanf("%lld",&T);
- while (T--) {
- scanf("%lld%lf%lf",&n,&h,&r);
- low=h;high=0;
- for (int i = 1;i <= n;i++) {
- scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].z);
- low=min(low,s[i].z);
- high=max(high,s[i].z);
- }
- if (low-r>0||high+r<h) {
- printf("No\n");
- continue;
- }
- for (int i = 0;i <= n+1;i++) f[i]=i;
- for (int i = 1;i <= n;i++) {
- if (s[i].z-r<=0) Union(0,i);
- if (s[i].z+r>=h) Union(i,n+1);
- }
- for (int i = 1;i < n;i++)
- for (int j = i+1;j <= n;j++)
- if (dist(s[i],s[j])<=2*r)
- Union(i,j);
- if (getf(0)==getf(n+1)) printf("Yes\n");
- else printf("No\n");
- }
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。