{"id":294,"date":"2018-10-31T20:40:07","date_gmt":"2018-10-31T12:40:07","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=294"},"modified":"2018-11-07T16:35:12","modified_gmt":"2018-11-07T08:35:12","slug":"lp3958-noip2018-%e5%a5%b6%e9%85%aa","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2018\/10\/31\/lp3958-noip2018-%e5%a5%b6%e9%85%aa\/","title":{"rendered":"lp3958 NOIP2017 \u5976\u916a"},"content":{"rendered":"

\u7b80\u5355\u7ed3\u8bba+\u5e76\u67e5\u96c6+\u5927\u529b\u6a21\u62df
\n\u6ce8\u610f\u5e76\u67e5\u96c6\u4e0d\u8981\u5199\u6302\u3002
\n\u53e6\uff1a\u8bb0\u4f4flong double\u7684\u8303\u56f4\u5c0f\u4e8elong long<\/p>\n

#include<iostream>\r\n#include<cstdio>\r\n#include<cstring>\r\n#include<cmath>\r\nusing namespace std;\r\n\r\n#define eps 1E-9\r\nlong long n,h,r;\r\ninline double clac(const long long &x1,const long long &y1,const long long &z1,const long long &x2,const long long &y2,const long long &z2){\r\n    return (double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));\r\n}\r\nlong long f[1005],x[1005],y[1005],z[1005];\r\ninline long long fa(const long long &x){\r\n    return (f[x]==x)?(x):(f[x]=fa(f[x]));\r\n}\r\ninline void uni(const long long &x,const long long &y){\r\n    (fa(x)==fa(y))?0:f[fa(x)]=fa(y);\r\n}\r\nbool up[1005],dn[1005];\r\nvoid init(){\r\n    scanf(\"%lld%lld%lld\",&n,&h,&r);\r\n    memset(up,0,sizeof(up));\r\n    memset(dn,0,sizeof(dn));\r\n    for(int i=1;i<=n;++i){\r\n        f[i]=i;\r\n    }\r\n    long long nx,ny,nz;\r\n    for(int i=1;i<=n;++i){\r\n        scanf(\"%lld%lld%lld\",&nx,&ny,&nz);\r\n        x[i]=nx;\r\n        y[i]=ny;\r\n        z[i]=nz;\r\n        if(z[i]<=r){\r\n            dn[i]=1;\r\n        }\r\n        if(h-z[i]<=r){\r\n            up[i]=1;\r\n        }\r\n    }\r\n    for(int i=1;i<=n;++i){\r\n        for(int j=1;j<=n;++j){\r\n            if(fa(i)==fa(j)){\r\n                continue;\r\n            }\r\n            if((double)(r*2)>=clac(x[i],y[i],z[i],x[j],y[j],z[j])){\r\n                uni(i,j);\r\n            }\r\n        }\r\n    }\r\n    for(int i=1;i<=n;++i){\r\n        if(!dn[i]){\r\n            continue;\r\n        }\r\n        for(int j=1;j<=n;++j){\r\n            if(!up[j]){\r\n                continue;\r\n            }\r\n            if(fa(i)==fa(j)){\r\n                puts(\"Yes\");\r\n                return;\r\n            }\r\n        }\r\n    }\r\n    puts(\"No\");\r\n} \r\nint main(){\r\n    int T;\r\n    scanf(\"%d\",&T);\r\n    while(T--){\r\n        init();\r\n    }\r\n    return 0;\r\n}<\/code><\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
\u7b80\u5355\u7ed3\u8bba+\u5e76\u67e5\u96c6+\u5927\u529b\u6a21\u62df \u6ce8\u610f\u5e76\u67e5\u96c6\u4e0d\u8981\u5199\u6302\u3002 \u53e6\uff1a\u8bb0\u4f4flong double\u7684\u8303\u56f4\u5c0f\u4e8elong long  … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201clp3958 NOIP2017 \u5976\u916a\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10,25,8,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/294"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=294"}],"version-history":[{"count":3,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/294\/revisions"}],"predecessor-version":[{"id":361,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/294\/revisions\/361"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=294"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=294"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=294"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}