Задача на геометрию (Delphi, C++)

[Demius]

Добрый день.

Даны координаты N точек и число S. Построили минимальную выпуклую оболочку (МВО), включающую в себя эти точки. Необходимо вывести максимально возможную площадь многоугольника (без самопересечений, выпуклость не гарантируется), получившегося изменением границы МВО и состоящего из указанных точек, не превышающую S.

Пример входных данных
4
1.0 1.0
-1.0 1.0
-1.0 -1.0
1.0 -1.0
4.0

Пример выходных данных
2.0


Необходим самый эффективный алгоритм решения.

[evg_m]

Необходимо вывести максимально возможную площадь многоугольника

Пример выходных данных
2

а я нашел больший.

[Demius]

а я нашел больший.

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

Вот рисунок, описывающий пример.


ABCD - это МВО, ACD - это один из многоугольников, удовлетворяющих условию задачи.

[evg_m]

имеем выпуклый многоугольник включающий в себя все точки.
Значит мы можем от него только отрезать.
максимальный из оставшихся будет если отрежем минимальный.
Мы можем отрезать любой многоугольник. Любой многоугольник (из отрезанных) можно нарезать на треугольники, каждый из который будет удовлетворять условию задачи и иметь меньшую площадь. Значит отрезаем треугольник.
Минимальный треугольник который мы можем отрезать соединяет три последовательные вершины.(т.к. МВО).
проверяем перебором и выбираем.

Минимальный треугольник который мы можем отрезать соединяет три последовательные вершины.(т.к. МВО).

НЕВЕРНО!
Минимальный треугольник ДВЕ последовательные вершины исходного + одна точка внутри(ближайшая к прямой проходящей через наши вершины).
если таких нет, то первоначальный вариант (три вершины).

P.S. три вершины это тоже две +одна точка внутри (только "внутри" включает и границы).
из МВО следует что ближайшие к прямой и являющиеся вершинами оболочки будут "ближайшими" (соседними) вершинами.

[Demius]

Пример входных данных
9
-2.0 2.0
2.0 -2.0
-2.0 -2.0
2.0 2.0
0.0 0.0
1.0 1.0
-1.0 1.0
-1.0 -1.0
1.0 -1.0
1.00008

Пример выходных данных
1.0



Будет ли работать на этом примере ваш алгоритм эффективно?

[evg_m]

Необходимо вывести максимально возможную площадь многоугольника

Пример выходных данных
1.0

получившегося изменением границы МВО и состоящего из указанных точек, не превышающую S.

L(ABCD)=(2-(-2))*4 =16
L(HEI)=(1-(1))+sqrt(2)*2=2+1,4*2=4,8
L2-L1=16-4,8 >S =1,00008

Будет ли работать на этом примере ваш алгоритм эффективно?

по сравнению с полным перебором вариантов да.
Но есть еще куда стремиться.
В анализе нигде не учитывается что изменение должно быть <S.

[Demius]

Спасибо. Попробую реализовать.