两天中唯一的良心题，然而我在考场上蜜汁 RE 成70...
做法应该很多，朴素做法应该有 并查集 和 搜索 ；
我打的 并查集，不过好像 DFS 快的一批；
思路很简单，就是把能连在一起的洞并成同一个集合；
最后要查询一下底面和顶面是否在同一集合中；
就完了（好裸啊然而我就是没AC）。
复杂度 O（n2×T）
AC代码如下，个人感觉还比较清晰（244 ms 2183 kb）：
#include<bits/stdc++.h> #define m(a,b) memset(a,b,sizeof(a)) // 懒.. #define ll long long using namespace std; int f[1002]; struct _{ // 表示点的结构体 int x,y,z; }a[1002]; inline bool cmp(_ a,_ b){ // 快排专属 return a.z<b.z; } inline ll q(ll x){ // 平方（还不是懒...） return x*x; } inline double dis(_ a,_ b){ // 两洞距离 return (double)sqrt(q(a.x-b.x)+q(a.y-b.y)+q(a.z-b.z)); } int find(int x){ // 并查集————查询 if(f[x]==x) return x; return f[x]=find(f[x]); } void bing(int a,int b){ // 并查集————合并 int x=find(a),y=find(b); f[x]=y; } inline void init(){ // 初始化 m(a,0),m(f,0); } int main(){ int n,t,h,r; scanf("%d",&t); while(t--){ init(); scanf("%d%d%d",&n,&h,&r); for(int i=1;i<=n+1;i++) f[i]=i; // 0是底面，n+1是顶面 for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); sort(a+1,a+n+1,cmp); // 按 z 排序，加快速度 for(int i=1;i<n;i++) for(int j=i+1;j<=n&&a[j].z-(r<<1)<=a[i].z;j++) if(dis(a[i],a[j])<=r<<1) bing(i,j); // 将距离小于 2*r 的洞合并 for(int i=1;i<=n;i++) if(a[i].z<=r) bing(0,i); // 把洞和顶面、 for(int i=n;i>0;i--) if(a[i].z>=h-r) bing(i,n+1); // 底面合并 if(find(0)==find(n+1)) printf("Yes "); else printf("No "); } return 0; }
%%% 写 扫描线 的 Dalao %%%
By The_Seventh
2017-12-23 18:08:34