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

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

Восстановить пароль Регистрация
 
Lockin
Сообщений: n/a
17.05.2013, 00:06     Найти не пересекающиеся треугольники #1
Народ, прошу помогите, преподаватель резко с паскаля перепрыгнул на C++, помогите сделать задачу.
Дано множество треугольников на плоскости координатами трех точек - вершин треугольника. Найти треугольник не пересекающийся с другими.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2013, 00:06     Найти не пересекающиеся треугольники
Посмотрите здесь:

C++ 3 взаимно пересекающиеся окружности
Определить, имеются ли среди этих окружностей три параллельно пересекающиеся C++
C++ Треугольники (C\C++)
Треугольники C++
Треугольники C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dev-a1056
 Аватар для dev-a1056
228 / 95 / 4
Регистрация: 16.04.2013
Сообщений: 315
Записей в блоге: 2
17.05.2013, 00:15     Найти не пересекающиеся треугольники #2
причем тут вообще язык программирования? давай так: ты пишешь псевдокод, а я перевожу все это дело в с++ или переформулируй задачу: "Мне лень, решите за меня, а я скажу спасибо".
Lockin
Сообщений: n/a
17.05.2013, 00:41     Найти не пересекающиеся треугольники #3
Цитата Сообщение от dev-a1056 Посмотреть сообщение
"Мне лень, решите за меня, а я скажу спасибо".
Мне лень, прошу помогите.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
17.05.2013, 00:48     Найти не пересекающиеся треугольники #4
Цитата Сообщение от Lockin Посмотреть сообщение
Мне лень, прошу помогите.
Мне лень, извините.

Хинт: векторное произведение.
dev-a1056
 Аватар для dev-a1056
228 / 95 / 4
Регистрация: 16.04.2013
Сообщений: 315
Записей в блоге: 2
17.05.2013, 02:04     Найти не пересекающиеся треугольники #5
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 использовать и определять какому треугольнику принадлежит тот или иной отрезок
а основа алгоритма по ссылкам. Удачи.
Yandex
Объявления
17.05.2013, 02:04     Найти не пересекающиеся треугольники
Ответ Создать тему
Опции темы

Текущее время: 01:47. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru