10301. Кольца и клей

На полу расположено n колец. Все точки пересечения колец смазаны клеем. При этом ни одно из колец не приклеено к полу. Необходимо найти и поднять конструкцию, содержащую наибольшее количество колец. Все кольца являются абсолютно тонкими.

Вход. Каждый тест начинается количеством колец на полу n (0 £ n < 100). Каждая из следующих n строк содержит координаты центра кольца и его радиус. Последний тест содержит n = –1 и не обрабатывается.

Выход. Для каждого теста в отдельной строке вывести наибольшее количество колец, находящихся в одной конструкции.

Пример входа

4

0.0 0.0 1.0

-1.5 -1.5 0.5

1.5 1.5 0.5

-2.0 2.0 3.5

3

3.0 2.0 2.0

0.0 -0.5 1.0

0.0 0.0 2.0

5

-2.0 0.0 1.0

1.0 -1.0 1.0

0.0 1.0 0.5

2.0 0.0 1.0

-1.0 1.0 1.0

-1

Пример выхода

The largest component contains 4 rings.

The largest component contains 2 rings.

The largest component contains 3 rings.

РЕШЕНИЕ

графы, компоненты связности

Анализ алгоритма

Рассмотрим неориентированный граф, где каждому кольцу соответствует вершина. Между двумя вершинами присутствует ребро, если соответствующие им кольца пересекаются. В задаче необходимо найти компоненту связности с наибольшим количеством вершин.

Реализуем систему непересекающихся множеств. Объявим массив deg, значение deg[i] будет содержать количество элементов во множестве, в котором находится вершина i, если i – представитель множества, и deg[i] = 0 иначе. Остается найти и вывести максимальное значение в массиве deg.

Реализация алгоритма

Максимальное количество колец в тесте 100, положим

#define MAX 101

Объявим рабочие массивы. Центр i - го кольца находится в (x[i], y[i]), радиус в r[i].

int mas[MAX], deg[MAX];

double x[MAX], y[MAX], r[MAX];

Функция поиска представителя элемента n.

int Repr(int n)

{

while (n != mas[n]) n = mas[n];

return n;

}

Объединение деревьев, содержащих элементы x и y.

void Union(int x,int y)

{

int x1 = Repr(x),y1 = Repr(y);

if (x1 == y1) return;

mas[x1] = y1;

}

Проверяем, пересекаются ли кольца i и j. Значение d равно расстоянию между центрами колец. Если оно больше суммы радиусов колец (или меньше разности радиусов), то кольца не пересекаются.

int intersect(int i, int j)

{

double d = (x[i]-x[j])*(x[i]-x[j]) + (y[i] - y[j])*(y[i]-y[j]);

if ((d > (r[i] + r[j])*(r[i] + r[j])) ||

(d < (r[i] - r[j])*(r[i]-r[j]))) return 0;

return 1;

}

Основная часть программы. Считываем входные данные.

while(scanf("%d",&n), n != -1)

{

for(i = 0; i < n; i++)

scanf("%lf %lf %lf",&x[i],&y[i],&r[i]);

for(i = 0; i < n; i++) mas[i] = i;

Если кольца i и j пересекаются, то объединяем их в одну компоненту.

for(i = 0; i < n - 1; i++)

for(j = i + 1; j < n; j++)

if (intersect(i,j)) Union(i,j);

memset(deg,0,sizeof(deg));

Для каждой вершины i ищем ее представителя j и увеличиваем значение deg[j] на 1.

for(i = 0; i < n; i++) deg[Repr(i)]++;

Ищем множество с наибольшим количеством вершин.

for(res = i = 0; i < n; i++)

if (deg[i] > res) res = deg[i];

Выводим ответ. Если количество колец равно 1, то согласно условию задачи выводим слово ring, иначе rings.

printf("The largest component contains %d ring",res);

if (res != 1) printf("s"); printf(".\n");

}