思路
问题中有两个需要注意的点,一个是空洞和空洞有合并的情况,另一个是合并后空洞的最大高度。因此,合并父节点的情况可以采用并查集的方式来维护,而对于最大高度的情况,思路是保存每个空洞的最高点,然后查询空洞根父亲节点的高度。然而这种思路还有一个比较重要的注意事项,即:能否有一个空洞的最低点小于0。如果所有空洞的最低点都大于0,一定是不可以的。所以维护一个st数组来保证哪些节点最低点是小于0的,以此保证其根父亲节点有意义。
另外,虽然最开始采用的是dis的平方进行比较,但考虑到r数据范围到1e9,所以应该采用开方后比较,并使用ll。
代码
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-9; const int INF = 0x3f3f3f3f; const ll MAXN = 1e3+10; ll fa[MAXN]; ll hei[MAXN]; ll st[MAXN]; ll cnt = 0; struct Node{ ll x; ll y; ll z; }nod[MAXN]; void init(){ for(ll i=0;i<MAXN;i++){ fa[i] = i; } cnt = 0; memset(hei,0,sizeof(hei)); memset(nod,0,sizeof(nod)); memset(st,0,sizeof(st)); return ; } ll dis(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2){ return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)+(z2-z1)*(z2-z1); } ll find(ll x){ if(fa[x]==x) return x; else{ return fa[x] = find(fa[x]); } } ll merge(ll x,ll y){ ll fx = find(x); ll fy = find(y); if(fx==fy) return 0; else{ if(hei[fx]>hei[fy]){ fa[fy] = fx; }else{ fa[fx]=fy; } return 1; } } int main(){ ll T; while(~scanf("%lld",&T)){ while(T--){ init(); ll n,h,r; scanf("%lld %lld %lld",&n,&h,&r); for(ll i=0;i<n;i++){ Node cur; scanf("%lld %lld %lld",&cur.x,&cur.y,&cur.z); hei[i] = cur.z+r; if(cur.z-r<=0){ st[cnt++] = i; } nod[i] = cur; } for(ll i=0;i<n;i++){ for(ll j=0;j<i;j++){ Node n1 = nod[i]; Node n2 = nod[j]; //printf("dis:%d\n",dis(n1.x,n1.y,n1.z,n2.x,n2.y,n2.z)); if(sqrt(1.0*dis(n1.x,n1.y,n1.z,n2.x,n2.y,n2.z))<2*r+eps){ merge(i,j); } } } ll flag= 0; for(ll i=0;i<cnt;i++){ ll father = find(st[i]); if(hei[father]>=h){ flag = 1; printf("Yes\n"); break; } } if(flag==0){ printf("No\n"); } } } return 0; }
全部评论
(0) 回帖