Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Программа пропускает второй и третий вводы данных http://www.cyberforum.ru/cpp-beginners/thread844509.html
Добрый день. При выполнении программки после ввода первых данных пропускает ввод остальных и сразу выдает результат. Подскажите пожалуйста в чем проблема! http://pikucha.ru/iaUnu/thumbnail/8.jpeg #include <iostream> #include <conio.h> #include <cmath> using namespace std; int main() { setlocale(LC_ALL, "rus");
C++ Задачка с двумерным массивом (Осуществить циклический сдвиг элементов) Ребят подскажите пожалуйста код программы) 2 дня сидел над лабараторками, уже башня не варит: Осуществить циклический сдвиг элементов прямоугольной матрицы на n элементов справа или вниз (в зависимости от введенного режима), n может быть больше количества элементов в строке или столбце. http://www.cyberforum.ru/cpp-beginners/thread844506.html
C++ работа с бинарными файлами в языке c (Прочитать действительные четырехбайтные элементы)
Написать программу для создания исходного двоичного файла чисел с произвольным количеством элементов.Прочитать из файла действительные четырехбайтные элементы
Дан массив 10х10, нужно чтобы показывал три самых максимальных повторений с перечислением повторяющихся элементов? C++
Дан массив 10х10, нужно чтобы показывал три самых максимальных повторений с перечислением повторяющихся элементов? 10 10 1 2 3 4 5 6 7 8 9 10 -1 2 -3 4 -5 6 -7 8 -9 10 10 9 8 7 6 5 4 3 2 1 -5 -6 -7 -8 -9 1 2 3 4 5 5 4 3 2 1 10 9 8 7 6 5 1 2 3 4 5 6 7 8 9 10 -1 2 -3 4 -5 6 -7 8 -9 10
C++ Найдите суммы элементов матрицы по строкам http://www.cyberforum.ru/cpp-beginners/thread844460.html
Здравствуйте товарищи (вернее сказать "Вечер добрый" (это если по Москве)) Сегодня решил сделать пару задачек на тему квадратных матриц. При реализации задач возникли некоторые вопросы и трудности (поясню ниже кода). Собственно, вот и код: #include <iostream> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std;
C++ нужно чтоб нашлась страна и все данные об этой стране вывелись в таблицу... Помогите с поиском по файлу ну не как не получается его сделать.... В файле записано: Страна Столица Валюта ну вот так ... ... ... подробнее

Показать сообщение отдельно
dev.nikor
25 / 26 / 1
Регистрация: 26.07.2010
Сообщений: 297

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

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

Здравствуйте, есть вот такая задача: На плоскости задано множество окружностей. Две окружности 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;
}
Вот только дальше я понятия не имею что нужно сделать, что бы найти наибольшее множество несвязанных окружностей. Подскажите пожалуйста, как дальше поступить.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru