万湖之国的形成

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;
typedef pair<double, double> p;
typedef pair<p, double> pi;
map<ll, ll> fa;
struct g
{
    double x, y, r;
    bool operator < (const g b)
    {
        return x+r<b.x+b.r;
    }//运算符重载,按照右端点排序
}a[100050];

ll find(int i)
{
    if(fa[i] == i)
        return i;
    return fa[i] = find(fa[i]);
}

int main()
{
    int n, m;//使用m来顶替n,避免对n进行操作
    cin >> n;
    m = n;
    for(int i = 0; i < n; ++i){
        cin >> a[i].x >> a[i].y >> a[i].r;
        fa[i] = i;
    }
    sort(a, a+n);
    for(int i = 0; i < n; ++i){
        for(int j = i-1; j >= 0; --j){
            if(a[j].x+a[j].r <= a[i].x-a[i].r)
                break;//两个圆没有交集,不考虑,并且由于圆的集合a是按右端点排序,所以不用继续考虑更左边的右端点,直接break
            if((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y) < (a[i].r+a[j].r)*(a[i].r+a[j].r)){
                //如果两个圆有交集
                ll l = find(i), r = find(j);//找两个圆的根
                if(fa[l] != r){//如果两个圆还没有被设为同根,m-1(什么时候出现同根呢?
                                 //比如ABC三连环的情况,C和A也有交集,此时就出现AC已经同根的情况)
                    m--;//使用m来顶替n,避免对n进行操作
                    fa[l] = r;//设为同根
                }
            }
        }
    }
    cout << m;
    return 0;
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容