NOIP 2017 Day2 T1 奶酪

2018-06-17 21:26:43来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Luogu题面

两天中唯一的良心题,然而我在考场上蜜汁 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\n");
        else printf("No\n");
    }
    return 0;
}

 

 

%%% 写 扫描线 的 Dalao %%%

 

By  The_Seventh

2017-12-23 18:08:34

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++中this指针的用法详解

下一篇:今天起开始写博客啦!