分析：并查集、计算几何。判断每两个圆环是否黏在一起即可，利用并查集记录。
注意：1.输出格式 0 rings。2.是圆环不是圆。3.并查集合并前要判断；把相同集合的合并会重复计数 ( ) 。
#include#include #include #include using namespace std; typedef struct rnode { double x,y,r; }ring; ring R[105]; double dist( ring a, ring b ) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } //union_set int sets[105]; int sums[105]; int rank[105]; //返回根节点 int Find( int a ) { if ( a != sets[a] ) sets[a] = Find( sets[a] ); return sets[a]; } //合并集合 void Union( int a, int b ) { if ( rank[a] < rank[b] ) { sets[a] = b; sums[b] += sums[a]; }else { if ( rank[a] == rank[b] ) rank[a] ++; sets[b] = a; sums[a] += sums[b]; } } //union_set end int main() { int n; while ( ~scanf("%d",&n) && n > = 0 ) { for ( int i = 0 ; i < n ; ++ i ) { scanf("%lf%lf%lf",&R[i].x,&R[i].y,&R[i].r); rank[i] = 1;sets[i] = i;sums[i] = 1; } for ( int i = 0 ; i < n ; ++ i ) for ( int j = i+1 ; j < n ; ++ j ) { if ( dist( R[i], R[j] )-1e-6 < fabs( R[i].r+R[j].r ) && dist( R[i], R[j] )+1e-6 > fabs( R[i].r-R[j].r ) ) if ( Find(i) != Find(j) ) Union( Find( i ), Find( j ) ); } int max = 0; for ( int i = 0 ; i < n ; ++ i ) if ( max < sums[i] ) max = sums[i]; //万恶的输出啊， ( ) if ( max > 1 || !max ) printf("The largest component contains %d rings.\n",max); else printf("The largest component contains 1 ring.\n"); } return 0; }