#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;
}
万湖之国的形成
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。