Вписать в многоугольник прямоугольник максимальной площади

[mitrik]

Попробовал вписывать эллипс - явно не катит, ибо видно, что можно вписать прямоугольник большей площади, его, конечно, можно строить относительно этого эллипса,но геморроя при это предостаточно.

Не совсем понял как строить квадрат на диагоналях, можно Вы чуть-чуть подробнее объясните?

[slavav]

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