Странная задача С. I курс.

[EniOk]

На плоскости задано множество окружностей. Две окружности A и B назовём связанными, если они пересекаются либо существует третья окружность C заданного множества, связанная с A и B. Выбрать максимальное подмножество попарно не связанных друг с другом окружностей.

Есть какие нибудь идеи как решить?
Сначала казалось просто все... Написав

int circlesCross(circle circle1, circle circle2)
{
    float distanceX = circle1.x - circle2.x;
    float distanceY = circle1.y - circle2.y;
    float distanceBetweenCenters = sqrt(distanceX * distanceX + distanceY * distanceY);
    return (distanceBetweenCenters <= circle1.r + circle2.r);
}

я понял что не знаю что делать дальше(

Ну да

struct CIRCLE {
float x, y, r;
char crossflag;
};

и еще

CIRCLE *circle = new CIRCLE[count];

то бишь их count штуков...

Проблема собственно в выборе максимального подмножества...
Ну так что - поможите?

[Sazary]

Ну вот на уровне идеи:
нужно создать что-то вроде матрицы смежности.
Допустим, у нас N окружностей.
Создаем матрицу. Вначале заполняем ее прямыми связями. То есть, если i-я окружность напрямую связана с j-й, то элемент (i,j) = 1.
Так заполнили матрицу. Далее проверяем непрямые связи.
Берем i-ю окружность. Для нее просматриваем все остальные. Для текущей j-й проверяем оставшиеся. Если и i-я и j-я окружности пересекают k-ю, то, опять же, элемент (i,j) = 1.
Все остальные ячейки будут нулями.

Матрица создана. Теперь ищем первый элемент, равный нулю. Это ячейка (i1,j1). Теперь для j1 ищем такой столбец k, для которого (j1,k)=0.
Ну вот так и доходим до конца, в поисках самой длинной цепочки.
Думаю, идея должна быть ясна.

[EniOk]

Ясно но не совсем понятно почему именоо цепочка с первым не нулевым элементом который нашелся в матрице связей будет длиннее других...

Хотя наверное возможно повторить это для всех таких элементов и посмотреть где получится больше окружностей... Но это же сколько действий! Все равно спасибо, идея интересная) Хотя и хотелось бы что то по проще)

[Sazary]

Сообщение от EniOk

Ясно но не совсем понятно почему именоо цепочка с первым не нулевым элементом который нашелся в матрице связей будет длиннее других...

Почему ненулевым? Наоборот. Ищем первый нулевой элемент. Т.к. это сразу дает 2 несвязанные окружности.

Вообще, навскидку, это не очень сложный вариант. И действий будет не так уж много. Возможно, понадобится рекурсивная функция для конечной части (по крайней мере, я бы делал именно через рекурсию).

[pu4koff]

Я бы создал матрицу связности окружностей, в которой элемент[x][y] == false означает, что окружности x и y не связанные.
Заполнять её можно в 2 этапа:
1) если окружности пересекаются
2) уже по данным этой матрицы легко определяем есть ли третья окружность, которая пересекает 2 окружности.
Примерно так:

цикл от (с = 0) до (с < число_окружностей)
начало
  если (матрица[c][a] и матрица[c][b]) значит
  начало
    матрица[a][b] = true;
    матрица[b][a] = true;
  конец
конец

Если моё предположение верно и я правильно понял задание, значит нужно всего-лишь найти столбец (ну или строку матрицы. как Вам больше нравится), в котором больше всего значений false.
Допустим, это будет столбец x. Тогда:

цикл от (y = 0) до (y < число окружностей)
начало
  если (матрица[x][y] == false) значит
    окружность y входит в искомое подмножество
конец

ЗЫ. Долго как я ответ писал

Так вот. Мне кажется, нет смысла в рекурсиях и мой вариант оптимальнее. Из условия задачи вытекает, что если окружность С не связана с окружностью А и не связана с окружностью Б, то и А не связана с Б. Таким образом, если найти такую окружность, которая не связана с бОльшим числом окружностей, то это и будет наибольшее подмножество несвязанных окружностей.

[Sazary]

pu4koff, так ведь нужно найти

максимальное подмножество попарно не связанных друг с другом окружностей.

А вы, как я понимаю, предлагаете брать окружность с наименьшим числом связей.

[EniOk]

Хмм... А если в варианте pu4koff после этого все что имеет false в строке у этой окружности опять проверять на взаимные связи - так это рекурента)

[pu4koff]

Сообщение от Sazary

А вы, как я понимаю, предлагаете брать окружность с наименьшим числом связей.

Я честно говоря до конца не понимаю это выражение: "максимальное подмножество попарно не связанных друг с другом окружностей".
А то под это подходит и простой поиск всех нулей в матрице. А и Б не связаны, значит добавляем в подмножество, т.к. они друг с другом попарно не связаны.

Нет. я в своём предположении был не прав. Сейчас на листочке нарисовал пару вариантов и 1 сработал, а во втором уже фигня получилась

[EniOk]

Сообщение от pu4koff

Я честно говоря до конца не понимаю это выражение: "максимальное подмножество попарно не связанных друг с другом окружностей".
А то под это подходит и простой поиск всех нулей в матрице. А и Б не связаны, значит добавляем в подмножество, т.к. они друг с другом попарно не связаны.

Нет. я в своём предположении был не прав. Сейчас на листочке нарисовал пару вариантов и 1 сработал, а во втором уже фигня получилась

Ну... Такое уж условие дали...

[Sazary]

Вот:


Как я понял, одна из самых длинных цепочек будет 1 -> 4 -> 8, т.к. они попарно не связаны.