#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;
}
万湖之国的形成
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
