学步园

坑姐题 = =。。。问你相互覆盖的圈圈最多有多少个。

输出是这个样子的，

....1 ring.

....0 rings.

....x rings.

另一方面 ，看错题了 = =。。应该用搜索的。。。神呐。。

#include <queue><br /> #include <stack><br /> #include <math.h><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <limits.h><br /> #include <string.h><br /> #include <string><br /> #include <algorithm><br /> using namespace std;<br /> const int MAX = 110;<br /> struct point{ double x,y;};<br /> struct circle{ point p; double r;};<br /> circle c[MAX];<br /> const double eps = 1e-6;<br /> bool dy(double x,double y) { return x > y + eps;} // x > y<br /> bool xy(double x,double y) { return x < y - eps;} // x < y<br /> bool dyd(double x,double y) { return x > y - eps;} // x >= y<br /> bool xyd(double x,double y) { return x < y + eps;} // x <= y<br /> bool dd(double x,double y) { return fabs( x - y ) < eps;} // x == y<br /> double disp2p(point a,point b)<br /> {<br /> return sqrt( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );<br /> }<br /> int sum,mmax;<br /> bool flag[MAX];<br /> void DFS(int i,int n)<br /> {<br /> if( sum > mmax ) mmax = sum;<br /> for(int k=0; k<n; k++)<br /> {<br /> if( flag[k] ) continue;<br /> double len = disp2p(c[i].p,c[k].p);<br /> if( xyd(len,c[i].r+c[k].r) && dyd(len+min(c[i].r,c[k].r),max(c[i].r,c[k].r)) )<br /> {<br /> sum++;<br /> flag[k] = 1;<br /> DFS(k,n);<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> int n;</p> <p> while( ~scanf("%d",&n) && n != -1 )<br /> {<br /> if( n == 0 )<br /> {<br /> printf("The largest component contains 0 rings./n");<br /> continue;<br /> }<br /> for(int i=0; i<n; i++)<br /> scanf("%lf%lf%lf",&c[i].p.x,&c[i].p.y,&c[i].r);</p> <p> mmax = 0;<br /> memset(flag,0,sizeof(flag));<br /> for(int i=0; i<n; i++)<br /> if( !flag[i] )<br /> {<br /> sum = 1; flag[i] = 1;<br /> DFS(i,n);<br /> }</p> <p> if( mmax > 1 )<br /> printf("The largest component contains %d rings./n",mmax);<br /> else<br /> printf("The largest component contains 1 ring./n");<br /> }<br /> return 0;<br /> }<br />