万湖之国的形成

#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;
}