Description
N国原是一块平原上，没有湖，直到一颗小行星撞入大气层碎成成千上万的碎片，碎片再撞击地面形成
一个一个的坑， 下雨之后，最终形成万湖之国。
现在科学家想用计算机模拟万湖之国形成过程，假设每一块碎片撞击地面，都撞出一个圆形坑，现在知道
每一个碎片造成的坑的圆心和半径，问每个坑都注满水后，最终形成多少个湖？
输入格式
第一行一个整数N，1<=N<=100,000，表示坑的数量
此后N行，每一行三个double实数，前两个数是圆心的坐标x和y，最后一个数是圆半径（不大于1000）
(数据随机产生，分布均匀)
输出格式
湖的个数
输入样例
3
0 0 5
10 0 5
11.1 0 2.5
输出样例
2
#include <iostream>#include <algorithm>using namespace std;int book[100050]; //标记数组struct Circle{double x;double y;double r;};Circle circle[100050];bool compare(Circle a,Circle b){return a.x+a.r<b.x+b.r; //以圆的右端点排序}int Find(int k){if(book[k]==k) return k; //如果没有被合并过，返回父节点的值else return book[k]=Find(book[k]); //如果该圆坑被合并过，找到父节点的值// !!!return book[k]=Find(book[k])}int main(){int n;int num;cin>>n;num=n;for(int i=0; i<n; i++){cin>>circle[i].x>>circle[i].y>>circle[i].r;book[i]=i; //一开始，每个圆坑都是自己的父节点，i就是父节点的值}sort(circle,circle+n,compare);for(int i=0; i<n; i++){for(int j=i-1; j>=0; j--){if(circle[j].x+circle[j].r<=circle[i].x-circle[i].r){break;}if(((circle[j].x-circle[i].x)*(circle[j].x-circle[i].x)+(circle[j].y-circle[i].y)*(circle[j].y-circle[i].y))<(circle[j].r+circle[i].r)*(circle[j].r+circle[i].r)){int m,n;m=Find(i); //找到i父节点的值n=Find(j); //找到j父节点的值if(m!=n) //如果i，j父节点的值不同{num--; //圆坑数量-1book[m]=n; //再把两个圆坑合并为1个，父节点的值改为同一个}}}}cout<<num<<endl;return 0;}
参考原文：
18233 万湖之国的形成_Del_G的博客-CSDN博客18233万湖之国的形成时间限制:2500MS 内存限制:65535K提交次数:0 通过次数:0题型: 编程题语言: G++;GCC;VCDes.../Qinie_/article/details/80831081?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165408751716782391890156%2522%252C%2522scm%2522%253A%25220713.130102334..%2522%257D&request_id=165408751716782391890156&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-80831081-null-null.142^v11^pc_search_result_control_group,157^v12^new_style1&utm_term=18233+%E4%B8%87%E6%B9%96%E4%B9%8B%E5%9B%BD%E7%9A%84%E5%BD%A2%E6%88%90&spm=1018.2226.3001.4187
如果觉得《SCAU 18233 万湖之国的形成》对你有帮助，请点赞、收藏，并留下你的观点哦！
