PersonalCorpus 版 (精华区)

1144145 Big Guava ... 10301 Accepted
0:00.000 64 2002/10/04 13:06:24.479

bool dl[100][100];


int tryit(int n)
{
    int i,j,k;
    int p[100];
    bool used[100];
    
    for (i=0;i<n;i++) {
        for (j=i+1;j<n;j++) if (dl[i][j]) break;
        if (j<n) break;
    }
    if (i==n) return 0;
    memset(used,0,sizeof(used));
    p[0]=i;
    used[i]=true;
    i=0; j=1;
    while (i<j) {
        for (k=0;k<n;k++) if ((dl[p[i]][k])&&(!used[k])) {
            used[k]=true;
            dl[p[i]][k]=false;
            dl[k][p[i]]=false;
            p[j]=k;
            j++;
        }
        i++;
    }
    return i;
}
            

void main()
{
#ifndef ONLINE_JUDGE
    freopen("c:\\0acm\\uva\\i10301","r",stdin);
    freopen("c:\\0acm\\uva\\o10301","w",stdout);
#endif

    int i,j,k,n;
    float r[100][3],t;

    scanf("%d\n",&n);
    while (n!=-1) {
        for (i=0;i<n;i++) scanf("%f%f%f\n",&r[i][0],&r[i][1],&r[i][2]);

        memset(dl,0,sizeof(dl));
        for (i=0;i<n;i++) for (j=i+1;j<n;j++) {
            
t=(r[i][0]-r[j][0])*(r[i][0]-r[j][0])+(r[i][1]-r[j][1])*(r[i][1]-r[j][1]
);
            if ( (t>(r[i][2]-r[j][2])*(r[i][2]-r[j][2]))&&
                 (t<(r[i][2]+r[j][2])*(r[i][2]+r[j][2])) ) {
                dl[i][j]=true;
                dl[j][i]=true;
            }
            if 
((r[i][0]==r[j][0])&&(r[i][1]==r[j][1])&&(r[i][2]==r[j][2])) {
                dl[i][j]=true;
                dl[j][i]=true;
            }
        }
        if (n==0) k=0; else k=1;
        do {
            i=tryit(n);
            if (i>k) k=i;
        } while (i!=0);

        if (k==1) printf("The largest component contains %d ring.\n",
k);
            else  printf("The largest component contains %d rings.\n",
k);
        scanf("%d\n",&n);
    }
}