Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
dev.nikor
25 / 26 / 3
Регистрация: 26.07.2010
Сообщений: 297
1

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

21.04.2013, 19:18. Просмотров 546. Ответов 0
Метки c++ (Все метки)

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

Сначала я строю что-то типа матрицы смежности, в которой a[i][j]=1, если i-я и j-я окружности связанны, остальные элементы равны нулю.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int** CreateAdjacencyMatrix(std::vector<Circle>& circleCollection) {
    int size = circleCollection.size();
    int** adjMatrix = new int*[size];
    for(int i = 0; i < size; i++) {
        adjMatrix[i] = new int[size];
    }
 
    for(int i = 0; i < size; i++) {
        for(int j = 0; j < size; j++) {
            //Если окружности пересекаются
            if(CircleCross(circleCollection[i], circleCollection[j])){
                adjMatrix[i][j]=adjMatrix[j][i]=1;
            }else adjMatrix[i][j]=adjMatrix[j][i]=0;
         //Ищем смежную окружность, которая пересекается с 2мя текущими
            for(int k=0; k<size; k++){
                if(k==i||k==j)continue;
 
                if(CircleCross(circleCollection[i],    circleCollection[k])&&CircleCross(circleCollection[j], circleCollection[k]))
                    adjMatrix[i][j]=adjMatrix[j][i]=1;
            }
        }
    }
    return adjMatrix;
}
Вот только дальше я понятия не имею что нужно сделать, что бы найти наибольшее множество несвязанных окружностей. Подскажите пожалуйста, как дальше поступить.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.04.2013, 19:18
Ответы с готовыми решениями:

Определить номера попарно пересекающихся окружностей
Помогите решить задачу: Пересекающиеся окружности. Даны натуральные числа x1 y1...

Определить попарно номера окружностей, которые имеют хотя бы одну общую точку
Пересекающиеся окружности. Даны натуральные числа x1,y1,r1...,x(n),y(n),r(n),...

Найти максимальное по числу вершин подмножество
Задали сделать прогу на C++ собственно вот задача: Найти максимальное по числу...

Из заданного множества int чисел определить максимальное подмножество
Была поставлена задача: &quot;Из заданного множества int чисел определить...

Объединить два массива друг за другом
1. Даны 2 одномерных массива А и В по К элементов каждый. Создать 3-й массив С...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.04.2013, 19:18

Размещение панелек друг над другом в псевдографике
Не знал, куда такое задание кинуть, надеюсь, что попал по адресу. Если что...

Как объединить столбцы таблицы под друг другом?
Всем привет! я новичок в программировании. Заранее извиняюсь за тупой вопрос....

Вывести четыре следующих друг за другом гласных букв
Есть строка, состоящая из слов, разделенных любым количеством пробелов....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru