Cергей-4030>Это такая структура, которая имеет данную площадь при наименьшем - что? Правильно, при наименьшем периметре. Если поставить целевой функцией минимизацию периметра, "стены" уходят и все многоугольники получаются очень "человеческими" (см. вложение).
Да, если просто поиграть хочется, то конечно и с таким условием очень интересно играть.
Вряд ли нас модеры обругают, если мы тему так поменяем.
Однако и задача от Balancer-а может стать насущной. Я пока играю с ней.
Текущие мысли примерно такие. В полном графе для N вершин имеем N(N-1)/2 ребер.
Значит, можно построить новый граф. Ребра старого - его точки. А ребра нового - пересечения старых. Таким образом, имея в исходном условии запрет на самопересечения, матрица смежности нового графа (размерчиком (N(N-1)*N(N-1)/4-N(N-1)/2)/2-> ~N
4 ) является по сути словариком матерн... запрещенных фигур. N
4 тоже не сахар, конечно.
ИМХО алгоритм проверки на пересечение (при условии целочисленности координат) тоже можно сделать полностью целочисленным.
Сразу ясно, что словарик избыточен, т.к. описывает полный граф. Но что делать, и как оптимизировать алгоритм в этой части, я пока не знаю.
Идея-то все та же, на максимально более раннем этапе отсеять самопересекающиеся замкнутые ломаные.
При постройке каждого из (N-1)!/2 многоугольников мы смотрим по словарику, нет ли в его наборе пересекающихся ребер. Если так дубово подойти, то все ускорение сведется к тому, что мы последовательно для каждого ребра просматриваем, нет ли хотя бы одного ненулевого элемента над главной диагональю по индексам, соответствующим остальным ребрам.
Но на самом-то деле, зная о факте пересечения какой-то конкретной пары ребер, из списка разрешенных фигур вылетает нафиг целый класс, содержащий эту пару. Сколько в этом классе фигур замкнутых ломаных, проходящих через все точки, ИМХО можно прикинуть. Но главное - надо придумать так организовать цикл, перебирающий эти (N-1)!/2 ломаных, чтобы из рассмотрения наиболее естественно исключались классы ломаных, а не отдельные штуки. ИМХО, в случае успеха это грозит сведение сложности задачи к полиномиальной.