Вадим обожает треугольники так сильно, что при виде любого выпуклого многоугольника он разрезает его на треугольники, поэтому он называет себя современным обер-форшнейдером. Порезать многоугольник на треугольники можно невероятно большим количеством способов, но самые элегантные из них — это те, в которых все разрезания — это непересекающиеся диагонали исходного многоугольника.
Сегодня у мамы Вадима день рождения, в честь чего он подарил ей торт, который является выпуклым многоугольником. Сразу же Вадим вызвался поработать ножом, чтобы элегантно разделить весь торт на кусочки-треугольники. Поскольку Вадим не любит сладкое, в конце он выберет себе самый маленький по площади кусочек, однако он не хочет, чтобы кто-то это заметил. Для этого современному обер-форшнейдеру нужно подобрать такой способ элегантно разделить торт, чтобы часть, которая достанется ему, была наибольшего размера. Помогите Вадиму найти эту площадь.
Исходные данные
В первой строке дано единственное целое число N — количество вершин многоугольника (3 ≤ n ≤ 200).
В каждой из следующих N строк через пробел даны по целых два числа xi, yi — координаты вершин многоугольника в порядке обхода против часовой стрелки (−108 ≤ xi, yi ≤ 108).
Гарантируется, что многоугольник выпуклый.
Результат
В единственной строке выведите искомую площадь кусочка Вадима.
Ответ будет засчитан, если абсолютная или относительная погрешность числа не превосходит 10−9. Формально, пусть ваш ответ равен x, а ответ жюри равен y. Ваш ответ считается правильным, если |x − y|⁄max(1, |y|) ≤ 10−9.
Пример
исходные данные | результат |
---|
4
0 0
5 -1
8 3
0 4
| 11.5
|
Автор задачи: Вадим Баринов
Источник задачи: Уральская командная олимпиада по программированию 2021