ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2165. Обер-форшнейдер

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

Исходные данные

В первой строке дано единственное целое число N — количество вершин многоугольника (3 ≤ n ≤ 200).
В каждой из следующих N строк через пробел даны по целых два числа xi, yi — координаты вершин многоугольника в порядке обхода против часовой стрелки (−108xi, yi ≤ 108).
Гарантируется, что многоугольник выпуклый.

Результат

В единственной строке выведите искомую площадь кусочка Вадима.
Ответ будет засчитан, если абсолютная или относительная погрешность числа не превосходит 10−9. Формально, пусть ваш ответ равен x, а ответ жюри равен y. Ваш ответ считается правильным, если |xy|max(1, |y|) ≤ 10−9.

Пример

исходные данныерезультат
4
0 0
5 -1
8 3
0 4
11.5
Автор задачи: Вадим Баринов
Источник задачи: Уральская командная олимпиада по программированию 2021