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

Найти не пересекающиеся треугольники - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Консольный ввод/вывод вещественного массива размерои 5*5 http://www.cyberforum.ru/cpp-beginners/thread867795.html
Добрый вечер. Возможно обращаюсь не по адресу, но все же попытка не пытка. Раньше программировал только в Паскале, а тут вдруг в универе заставили сделать пару лабораторных в С++. Я в С++ не бум...
C++ Лексический и синтаксический анализ текста Доброго времени суток, нужно написать курсач по программированию - реализовать алгоритм лексического анализа предложений - реализовать алгоритм синтаксического анализа предложений, построить... http://www.cyberforum.ru/cpp-beginners/thread867771.html
Задача на поиск максимума C++
Задача с (acm.timus.ru) Вот условия Рассмотрим последовательность чисел ai, i = 0, 1, 2, …, удовлетворяющих следующим условиям: a0 = 0 a1 = 1 a2i = ai a2i + 1 = ai + ai + 1 для каждого i =...
Динамический линейный список с одной связью C++
Здравствуйте. Нужно с бинарного файла прочесть данные и записать их в динамический линейный список с одной связью. Компилятор - VS 2010. Записываю так: FILE *f; f=fopen("file.bin","r+b");...
C++ Блочный алгоритм шифрования http://www.cyberforum.ru/cpp-beginners/thread867730.html
Ребят помогите с прогой. Реализовать нужно в билдере. Или хотя бы на код просто натолкните. Задание: Реализовать систему симметричного блочного шифрования, позволяющую шифровать и дешифровать...
C++ как создать текстовый файл и написать там данные? как создать текстовый файл и написать там данные? подробнее

Показать сообщение отдельно
dev-a1056
228 / 95 / 4
Регистрация: 16.04.2013
Сообщений: 315
Записей в блоге: 2
17.05.2013, 02:04
1. O(n*3^2) - тупо в лоб, для каждой стороны(отрезка) поискать пересечение со всеми другими сторонами, не принадлежащих этому треугольнику, если пересечение найдено удалять треугольники из списка. Это не интересно. И собственно вот тут: http://e-maxx.ru/algo/segments_intersection_checking можно посмотреть как определить факт пересечения двух отрезков.

2. O(n*3 log(n*3)) - используя Sweep line algorithm. можно модифицировать реализацию того же e-maxx:
http://e-maxx.ru/algo/intersecting_segments

Короче тебе остается только правильно цикл for использовать и определять какому треугольнику принадлежит тот или иной отрезок
а основа алгоритма по ссылкам. Удачи.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru