NOIP2017提高组DAY2T1 - 奶酪

题意

输入
每个输入文件包含多组数据。
输入文件的第一行，包含一个正整数 T，代表该输入文件中所含的数据组数。
接下来是 T 组数据，每组数据的格式如下：
第一行包含三个正整数 n， h 和 r， 两个数之间以一个空格分开，分别代表奶酪中空 洞的数量，奶酪的高度和空洞的半径。
接下来的 n 行，每行包含三个整数 x、 y、 z， 两个数之间以一个空格分开， 表示空 洞球心坐标为(x, y, z)。

输出
输出文件包含 T 行，分别对应 T 组数据的答案，如果在第 i 组数据中， Jerry 能从下 表面跑到上表面，则输出“Yes”，如果不能，则输出“No”（均不包含引号）。

样例输入
3
2 4 1
0 0 1
0 0 3
2 5 1
0 0 1
0 0 4
2 5 2
0 0 2
2 0 4
样例输出
Yes
No
Yes

【数据规模与约定】
对于 20%的数据， n = 1， 1 ≤ h , r ≤ 10,000，坐标的绝对值不超过 10,000。
对于 40%的数据， 1 ≤ n ≤ 8， 1 ≤ h , r ≤ 10,000，坐标的绝对值不超过 10,000。
对于 80%的数据，1 ≤ n ≤ 1,000， 1 ≤ h , r ≤ 10,000，坐标的绝对值不超过 10,000。
对于 100%的数据， 1 ≤ n ≤ 1,000， 1 ≤ h , r ≤ 1,000,000,000， T ≤ 20，坐标的 绝对值不超过 1,000,000,000

Experience

咬咬手指，扣扣脑袋，( ⊙ o ⊙ )啊！灵光一闪，$n^2$建图bfs跑一遍，就可以判是否能到达了。算了算复杂度$n^2\ast T$，沉思……应该能卡过去
然后稀里糊涂的写了一发，居然就A了！！！
然而正当我高高兴兴的时候，隔壁大佬cxr凑过来看了一眼，这不是并查集吗？
啥……
并……查……集……
感觉任督二脉突然被打通，一下子就发现自己傻逼了
判连通的话用并查集不就解决了吗？？？
还是太弱了啊……………………

Analysis

T1还是比较好做的
判两个洞是否相交（或相切）就是看它们球心的距离是否$<=2\ast r$
如果相交的话就将这两个洞合并（并查集实现）
判断是否和下部（或顶部）相通，就是看球心的位置$+-r$是否$<=0||>=h$
最后就判断一下0和顶部（n+1）是否在同一个集合里就可以了

Code

这个代码是贴的神仙zzh的，（毕竟我不是这样写的）

#include <bits/stdc++.h>
using namespace std;
const int Max=1010;
int t,n,h,r,flag,father[Max];
struct shu{long long x,y,z;};
shu a[Max];
inline int get_int()
{int x=0,f=1;char c;for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());if(c=='-') {f=-1;c=getchar();}for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';return x*f;
}
inline bool comp(const shu &a,const shu &b){return a.z<b.z;}
inline double calc(int i,int j){return sqrt(double(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z));}
inline int getfather(int v){return father[v]==v ? v : father[v]=getfather(father[v]);}
int main()
{t=get_int();while(t--){memset(a,0,sizeof(a));n=get_int(),h=get_int(),r=get_int();for(int i=1;i<=n;i++) a[i].x=get_int(),a[i].y=get_int(),a[i].z=get_int();sort(a+1,a+n+1,comp);for(int i=1;i<=n;i++) father[i]=i;if(a[n].z+r<h || a[1].z>r) {cout<<"No\n";continue;}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(calc(i,j)<=2*r){int fax=getfather(i),fay=getfather(j);if(fax!=fay) father[fay]=fax;}flag=0;for(int i=n;i>=1;i--){if(flag) break;if(a[i].z+r<h || flag) break;for(int j=1;j<=n;j++){if(a[j].z>r) break;if(getfather(j)==getfather(i)&&a[j].z+r>=0) {flag=1;break;}}}cout<<(flag ? "Yes\n" : "No\n");}return 0;
}

再放一份我的BFS代码
思路清晰，代码好写
（我不要脸）

#include<bits/stdc++.h>
#define in read()
#define N 1009
#define M 2000009
#define ll long long
using namespace std;
inline ll read(){char ch;int f=1;ll res=0;while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+ch-'0';ch=getchar();}return f==1?res:-res;
}
int T;
ll n,h,r;
struct node{double x,y,z;}p[N];
int nxt[M],to[M],head[N],ecnt=0;
bool vis[N];
void add(int x,int y){	nxt[++ecnt]=head[x];head[x]=ecnt;to[ecnt]=y;}
void init(){ecnt=0;memset(head,0,sizeof(head));
}
double Pow(double a) {return a*a;}
double calc(int x,int y){return sqrt(Pow(p[x].x-p[y].x)+Pow(p[x].y-p[y].y)+Pow(p[x].z-p[y].z));
}
bool bfs(){memset(vis,0,sizeof(vis));queue<int> q;q.push(0);while(!q.empty()){int u=q.front();q.pop();for(int e=head[u];e;e=nxt[e]){int v=to[e];if(v==n+1) return 1;if(!vis[v]) q.push(v),vis[v]=1;}}return 0;
}
int main(){T=in;int i,j,k;while(T--){init();n=in;h=in;r=in;for(i=1;i<=n;++i){p[i].x=in;p[i].y=in;p[i].z=in;if(p[i].z-r<=0) add(0,i),add(i,0);if(p[i].z+r>=h) add(n+1,i),add(i,n+1);}for(i=1;i<n;++i)for(j=i+1;j<=n;++j){double dis=calc(i,j);if(dis<=2*r) add(i,j),add(j,i);}if(bfs()) printf("Yes\n");else printf("No\n");}return 0;
}