传送门 https://www.luogu.org/problemnew/show/P3958#sub
思路:
模拟题. 用并查集求出所有 "连通块" , 判断是否有 "连通块" 的最顶上和最下方都不小于奶酪的范围.
- Code:
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- #include<cstring>
- #include<string>
- #include<cstdlib>
- #include<stack>
- #include<vector>
- #include<queue>
- #include<deque>
- #include<map>
- #include<set>
- using namespace std;
- #define lck_max(a,b) ((a)>(b)?(a):(b))
- #define lck_min(a,b) ((a)<(b)?(a):(b))
- #define INF 1e9+7
- typedef long long LL;
- const int maxn=1e3+7;
- LL T,n,h,r,up_cnt,down_cnt,fa[maxn];
- bool flag;
- struct hh
- {
- LL x,y,z,up,down;
- }t[maxn*maxn];
- inline LL read()
- {
- LL kr=1,xs=0;
- char ls;
- ls=getchar();
- while(!isdigit(ls))
- {
- if(!(ls^45))
- kr=-1;
- ls=getchar();
- }
- while(isdigit(ls))
- {
- xs=(xs<<1)+(xs<<3)+(ls^48);
- ls=getchar();
- }
- return xs*kr;
- }
- inline LL find(LL u)
- {
- return u==fa[u]?u:fa[u]=find(fa[u]);
- }
- inline double dis(LL u,LL v)
- {
- return sqrt((t[u].x-t[v].x)*(t[u].x-t[v].x)+(t[u].y-t[v].y)*(t[u].y-t[v].y)+(t[u].z-t[v].z)*(t[u].z-t[v].z));
- }
- int main()
- {
- freopen("cheese.in","r",stdin);
- freopen("cheese.out","w",stdout);
- T=read();
- while(T--)
- {
- flag=false,up_cnt=0,down_cnt=0;
- n=read();h=read();r=read();
- for(LL i=1;i<=n;i++) fa[i]=i;
- for(LL i=1;i<=n;i++)
- {
- t[i].x=read();t[i].y=read();t[i].z=read();
- if(t[i].z+r>=h) t[++up_cnt].up=i;
- if(t[i].z-r<=0) t[++down_cnt].down=i;
- for(LL j=1;j<i;j++)
- {
- if(dis(i,j)>2*r) continue;
- LL r1=find(fa[i]),r2=find(fa[j]);
- if(r1!=r2) fa[r1]=r2;
- }
- }
- for(LL i=1;i<=up_cnt;i++)
- for(LL j=1;j<=down_cnt;j++)
- {
- LL r1=find(t[i].up),r2=find(t[j].down);
- if(r1==r2) {flag=true;break;}
- }
- if(!flag) printf("No\n");
- else printf("Yes\n");
- }
- fclose(stdin);
- fclose(stdout);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2831809.html