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

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

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

Народ, прошу помогите, преподаватель резко с паскаля перепрыгнул на 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 использовать и определять какому треугольнику принадлежит тот или иной отрезок

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

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

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

Lockin
	17.05.2013, 00:41	3
	Сообщение от dev-a1056 "Мне лень, решите за меня, а я скажу спасибо". Мне лень, прошу помогите.

@OhMyGodSoLong ~ Эврика! ~ 1256 / 1005 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	17.05.2013, 00:48	4
	Сообщение от Lockin Мне лень, прошу помогите. Мне лень, извините. Хинт: векторное произведение. 0

@dev-a1056 228 / 95 / 27 Регистрация: 16.04.2013 Сообщений: 315 Записей в блоге: 2
	17.05.2013, 02:04	5
	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