Задача: Дано 3n точек на плоскости, причем никакие три из них не лежат на одной прямой. Построить множество n треугольников с вершинами в этих точках так, чтобы никакие два треугольника не пересекались и не содержали друг друга, а суммарная площадь этих треугольников была максимальной.
Пытаюсь найти правильный подход к задачке.
Я начал решать в лоб: сначала прохожу по всем точкам и записываю в двумерный массив все возможные треугольники.
То есть если дано 6 точек, то начало массива будет выглядеть так: [[0,1,2], [0,1,3], [0,1,4], [0,1,5], [0,2,3], [0,2,4], и т.д., где цифры в массиве - это индексы известных нам точек. Для 6 точек получается 20 разных треугольников. Для 9 точек - 84 треугольника и т.д.
Далее нужно, насколько я понимаю, сравнить каждый треугольник с каждым, чтобы выявить, какие 2 треугольника (в случае 6 точек) имеют наибольшую площадь и при этом не пересекаются. Я это реализую с помощью рекурсивной функции и получается, что для 20 треугольников будет 190 итераций (комбинаторика, сочетания из двадцати по два).
Но проблема в том, что если точек будет 9, то будет 84 возможных треугольника и уже 95284 итераций (84 по 3) и для 12 точек будет 220 треугольников и 94.966.795 итераций (220 по 4). А 15 точек программа уже вовсе не посчитает за адекватное время.
И вот проблема в том, что программа не должна крашится уже на 15-ти точках.
Я понимаю, что такой подход, по всей видимости, неправильный, но иного решения пока в голову не пришло
Не кидаю код, потому что прошу подсказать именно подход к задаче
На правах гипотезы могу предположить, что тут сработает триангуляция Делоне, потому что единичные треугольники, которые она выдает, наиболее близки к равносторонним (а значит, каждый имеет наибольную площадь при наименьшем периметре)
Суммарная площадь этих треугольников -- площадь области, ограниченной линиями, соединяющими наиболее удадённые от начала координат точки. А на треугольники бьётся любой многоугольник, о чём, ЕМНИП, есть соответствующая теорема.
Upd: см. картинку ниже. Полученный многоугольник лекго представим в виде двух кусочно-гладких функций, а значит площадь ищется очевидным образом с точностью до погрешности округления.
>Далее нужно, насколько я понимаю, сравнить каждый треугольник с каждым, чтобы выявить, какие 2 треугольника (в случае 6 точек) имеют наибольшую площадь и при этом не пересекаются
Перечитайте задание снова. Явно этого не требуется.
>И вот проблема в том, что программа не должна крашиться уже на 15ти точках.
А она крашится? Если да, то проверьте условие выхода из рекурсии, поскольку неверное условие может приводить к переполнению стека.
Армянское Радио, Alexander_The_Great, Вот только в задаче надо не триангуляцию строить. Иначе решение было бы очевидно (выпуклая оболочка, а дальше триангулировать рекурсивно как угодно. Никакие делоне тут не нужны). Дано 3n точек, надо построить на них n треугольников. Мне кажется, что труегольники не должны пересекаться в вершинах, но если вчитаться в условие, это явно нигде не сказано. Зависит от того, считается ли это за пересечение треугольников.
timaslov Уточните задачу - насколько велико n, надо ли все точки разбить на тройки, или трегольники могут касаться в вершинах?
Мне кажется, что труегольники не должны пересекаться в вершинах, но если вчитаться в условие, это явно нигде не сказано. Зависит от того, считается ли это за пересечение треугольников.
Зато есть явное условие - количество треугольников должно быть (Количество точек)/3 и в каждой точке должна быть вершина. Тоесть, условно, не получится из 9 точек занять только 7.
Wataru, мне кажется очевидным, что треугольники могут касаться в вершинах. А под пересечением подразумевается пересечение интервалов от вершины до вершины.
P.S.: да, я знаю, что это можно описать математически более изящно и лаконично.
Василий Банников, Вот про то, что в каждой точке должна быть вершина в условии как раз не сказано. Но мне кажется логичным, что оно подразумевается.
Alexander_The_Great, А там никакие 3 точки не лежат на одной прямой, поэтому пересечение по границе и не возможно. Ждем автора вопроса с уточнениями. Но я все же склоняюсь к тому, что нельзя касаться. Все-таки зачем треугольников в три раза меньше, чем точек? Если можно переиспользовать точки (и, соответственно, оставлять произвольное их количество неиспользуемыми вообще), то задача бы вообще не поменялась, будь точек N, а треугольников произвольное количество M <= N-2.
Wataru, возможно мы немного о разных вещах говорим.
Я полагаю, что подразумевается невозможность, к примеру, образования звезды Давида.
Т.е. нам следует исключить пересечения вне зарание заданных точек.
А вот про условие кратности трём -- да, нужно уточнение.
hint000 Это у вас итеративно выпуклая оболочка оставшегося множества откусывается как очередной слой?
Вообще можно преставить, что тругольник будет пересекать одну из оболочек в оптимальном решении. Преставьте маааленький ромб, вокруг него большой квадрат, а вокруг него еще более большой ромб. В ответе будут 4 трегуольника с вершинами из всех трех оболочек.
До 15 точек можно полным перебором сделать. Вам надо перебрать все разбиения 3n точек на тройки. Таких разбиений (3n)!/(3!)^n/n! для n=5 - это чуть больше миллиона.
Вы у себя перебираете все треугольники, даже если они имеют общие точки, это сильно раздувает количество вариантов.
Перебирать можно рекурсивно - берите первую точку без треугольника и пребирайте 2 оставшиеся, которые будут образовывать с ней треугольник. Помечайте их в треугольник и рекурсивно запускайтесь дальше. Потом откатывайте последние изменения и перебирайте другие варианты. Дальше надо проверить, что никакие 2 теругольника не пересекаются и не лежат друг в друге. Если это еще и делать по мере генерации, то можно неплохо ускорить решение за счет отсечения заведомо невозможных ваниантов. Может даже до 21 одной точки будет работать терпимо по скорости.
Какое-то геометрическое решение в голову что-то не приходит.
Wataru, Почему же, если построить эти треугольники по Делоне, а такое построение единственное, то останется только выбрать те, которые в сумме дадут наибольшую площадь, тут уже вариантов меньше
Владимир Скибин, И это даст не максимальную площадь, практически всегда. Ваши треугольники всегда не будут содержать внутри других точек. Но при этом могут касаться вершинами или сторонами. Т.е какие-то точки будут висеть неиспользованными. А в оптимальном решении может надо взять большой треугольник с кучей точек внутри. Это если, как вы описали, просто выбирать максимальные треугольники. Если же выбирать их так, чтобы они не касались, то такого набора может просто не быть в триангуляции Делоне. Какое свойство именно Делоне вы используете в решении? Можно же кучей разных способов построить триангуляцию.
Средний
