首页 > 其他 > 详细

计蒜客 奶酪 (并查集)

时间:2017-11-23 11:51:27      阅读:41      评论:0      收藏:0      [点我收藏+]

标签:long   con   print   知识   sca   clas   之间   mark   author   


链接 : Here!

思路 :

  • 其实这个是一道简单的并查集问题, 判断$Jerry$是否能从下表面跑到上表面, 其实质上是判断上表面和下表面是否连通, 因此这道问题就变成了判断连通性的问题了. 判断标准是如果$d <= 2 * r$ ($d$为两球心之间的距离), 那么就合并两个集合即可

思考 : 将知识穿成线索,做等价迁移,将复杂问题变成简单问题.

代码 :

/*************************************************************************
    > File Name: t13.cpp
    > Author: 
    > Mail: 
    > Created Time: 2017年11月21日 星期二 16时33分31秒
 ************************************************************************/

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;

#define MAX_N 1010
typedef long long ll;
int par[MAX_N];
int size[MAX_N];
ll n, h, r;

struct Point {
    ll x, y, z;
};

double check(Point a, Point b) {
    return (sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z)) <= 2 * r);
}

void init() {
    for (int i = 0 ; i < MAX_N ; ++i) {
        par[i] = i;
        size[i] = 1;
    }
}
int find(int x) {
    return x == par[x] ? x : (par[x] = find(par[x]));
}
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (size[x] > size[y]) {
        size[x] += size[y];
        par[y] = x;
    } else {
        size[y] += size[x];
        par[x] = y;
    }
}
int same(int x, int y) {
    return find(x) == find(y);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        init();
        Point data[MAX_N];
        scanf("%lld%lld%lld", &n, &h, &r);
        for (int i = 2 ; i <= n + 1 ; ++i) {
            scanf("%lld%lld%lld", &data[i].x, &data[i].y, &data[i].z);
        }
        // 先把能接触到地面的点加入到地面集合0中
        for (int i = 2 ; i <= n + 1 ; ++i) {
            if (fabs(0 - data[i].z) > r) continue;
            if (same(0, i)) continue;    
            merge(0, i);
        }
        // 再把能接触到上端的点加入到顶端集合1中
        for (int i = 2 ; i <= n + 1 ; ++i) {
            if (fabs(h - data[i].z) > r) continue;
            if (same(1, i)) continue;
            merge(1, i);
        }
        
        for (int i = 2 ; i <= n + 1 ; ++i) {
            for (int j = 2 ; j <= n + 1 ; ++j) {
                if (same(i, j)) continue;
                if (!check(data[i], data[j])) continue;
                merge(i, j);
            }
        }

        if (same(0, 1)) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

计蒜客 奶酪 (并查集)

标签:long   con   print   知识   sca   clas   之间   mark   author   

原文:http://www.cnblogs.com/WArobot/p/7883960.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号