ACM UVA 10301 (Rings and Glue)

题目： 

思路：

注意浮点数精度以及圆的内切外切。

代码：

//
// Author: xfye
// Status: AC
//

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>

using namespace std;

#define EPSINON  1e-6

int compareFloat(double f1, double f2)
{
    if (fabs(f1 - f2) < EPSINON) {
        return 0;   // equal
    }

    if (f1 - f2 < -EPSINON) {
        return -1;  // f1 < f2
    }

    return 1;       // f1 > f2
}


int g_max = 0;

struct Ring
{
    double x;
    double y;
    double r;
    int visited;
};

//
// Becarefull that all rings are of the doughnut kind (with a hole in them)
//
bool isTwoRingOverlapped(Ring* ring1, Ring* ring2)
{
    double distance = sqrt(( ring1->x - ring2->x ) * ( ring1->x - ring2->x ) + ( ring1->y - ring2->y ) * ( ring1->y - ring2->y ) );
    //cout << "ring1->r: " << ring1->r << endl;
    //cout << "ring2->r: " << ring2->r << endl;
    //cout << "distance: " << distance << endl;

    if (compareFloat(ring1->x, ring2->x) == 0 &&
        compareFloat(ring1->y, ring2->y) == 0 &&
        compareFloat(ring1->r, ring2->r) == 0) {
        return true;
    }

    if (compareFloat(distance, fabs(ring1->r - ring2->r)) < 0) {
        return false;
    }

    if (compareFloat(distance, ring1->r + ring2->r) > 0) {
        return false;
    }

    return true;
}

//
// Calculate the connections from rings[start] to the
// rings behind rings[start].
//
int calcConnections(Ring* rings, int ringsNum, int start)
{
    int ret = 1;

    rings[start].visited = 1;
    for (int i = 0; i < ringsNum; i++) {
        if (i == start || rings[i].visited) {
            continue;
        }
        //cout << start << "," << i << endl;
        if (isTwoRingOverlapped(&rings[start], &rings[i])) {
            if (!rings[i].visited && start < i) {
                ret += calcConnections(rings, ringsNum, i);
            } else {
                ret++;
            }
        }
    }

    if (g_max < ret) {
        g_max = ret;
    }

    return ret;
}

int main()
{
    int ringsNum = 0;
    Ring rings[100];


    cin >> ringsNum;
    while (ringsNum != -1) {
        memset(rings, 0, sizeof(rings));
        g_max = 0;
        for (int i = 0; i < ringsNum; i++) {
            cin >> rings[i].x >> rings[i].y >> rings[i].r;
        }

        for (int i = 0; i < ringsNum; i++) {
            if (!rings[i].visited) {
                calcConnections(rings, ringsNum, i);
            }
        }

        cout << "The largest component contains " << g_max;
        if (g_max == 1) {
            cout << " ring." << endl;
        } else {
            cout << " rings." << endl;
        }
        cin >> ringsNum;
    }
}