Although can be solved in O(N^3)
Here's the interesting paper: Optimal Area Triangulation
https://core.ac.uk/download/pdf/226134402.pdf
(haven't read yet)

Hint: Also include O(N^3) solution

I'm native Russian language speaker, but I really cannot understand what is required in the problem:

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

He doesn't like sweets, so he takes part of minimal size, but he wants to maximize size at the same time. WTF, where is the logic here, what does author want from us - to find maximin over all cuts, or something else?