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

17.05.2013, 00:06. **Показов** 1383. **Ответов** 4

Студворк — интернет-сервис помощи студентам

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

@dev-a1056 · 17.05.2013, 00:15

причем тут вообще язык программирования? давай так: ты пишешь псевдокод, а я перевожу все это дело в с++ или переформулируй задачу: "Мне лень, решите за меня, а я скажу спасибо".

17.05.2013, 00:41

Сообщение от dev-a1056

"Мне лень, решите за меня, а я скажу спасибо".

Мне лень, прошу помогите.

@OhMyGodSoLong · 17.05.2013, 00:48

Сообщение от Lockin

Мне лень, прошу помогите.

Мне лень, извините.

Хинт: векторное произведение.

@dev-a1056 · 17.05.2013, 02:04

1. O(n*3^2) - тупо в лоб, для каждой стороны(отрезка) поискать пересечение со всеми другими сторонами, не принадлежащих этому треугольнику, если пересечение найдено удалять треугольники из списка. Это не интересно. И собственно вот тут: http://e-maxx.ru/algo/segments... n_checking можно посмотреть как определить факт пересечения двух отрезков.

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

Короче тебе остается только правильно цикл for использовать и определять какому треугольнику принадлежит тот или иной отрезок

а основа алгоритма по ссылкам. Удачи.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

Lockin

	Найти не пересекающиеся треугольники 17.05.2013, 00:06. Показов 1383. Ответов 4 Метки нет (Все метки) Народ, прошу помогите, преподаватель резко с паскаля перепрыгнул на C++, помогите сделать задачу. Дано множество треугольников на плоскости координатами трех точек - вершин треугольника. Найти треугольник не пересекающийся с другими.

@dev-a1056 228 / 95 / 27 Регистрация: 16.04.2013 Сообщений: 315 Записей в блоге: 2
	17.05.2013, 00:15
	причем тут вообще язык программирования? давай так: ты пишешь псевдокод, а я перевожу все это дело в с++ или переформулируй задачу: "Мне лень, решите за меня, а я скажу спасибо". 0

@dev-a1056 228 / 95 / 27 Регистрация: 16.04.2013 Сообщений: 315 Записей в блоге: 2
	17.05.2013, 02:04
	1. O(n3^2) - тупо в лоб, для каждой стороны(отрезка) поискать пересечение со всеми другими сторонами, не принадлежащих этому треугольнику, если пересечение найдено удалять треугольники из списка. Это не интересно. И собственно вот тут: http://e-maxx.ru/algo/segments... n_checking можно посмотреть как определить факт пересечения двух отрезков. 2. O(n3 log(n*3)) - используя Sweep line algorithm. можно модифицировать реализацию того же e-maxx: http://e-maxx.ru/algo/intersecting_segments Короче тебе остается только правильно цикл for использовать и определять какому треугольнику принадлежит тот или иной отрезок а основа алгоритма по ссылкам. Удачи. 0