Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
dev.nikor
25 / 26 / 1
Регистрация: 26.07.2010
Сообщений: 297
#1

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

21.04.2013, 19:18. Просмотров 522. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Максимальное подмножество попарно не связанных друг с другом окружностей (C++):

Определить номера попарно пересекающихся окружностей - C++
Помогите решить задачу: Пересекающиеся окружности. Даны натуральные числа x1 y1 r1, ... xn, yn, rn, которые задают последовательность...

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

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

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

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

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

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

АТД список. Расположение одинаковых элементов друг за другом - C++
Здравствуйте! Подскажите, пожалуйста, как расположить одинаковые элементы друг за другом??? Например: Есть такой список: ...

Как правильно потоки должны взаимодействовать друг с другом? - C++
Добрый день. Встает вопрос по std::thread, а именно. Как несколько созданных потоков должны взаимодействовать друг с другом? Например...

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

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


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

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

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