ЗАДАЧА E
Новогодний торт
| Имя входного файла: | cake.in |
| Имя выходного файла: | cake.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
Новый год отмечают все, в том числе и такие легендарные личности, как Вася Пупкин. Новый 2009 год Вася будет встречать дома, куда пригласит N своих лучших друзей. Для них он решил приготовить свой знаменитый новогодний торт. По замыслу Васи, торт должен иметь форму выпуклого (N+3)-угольника. Тогда Вася будет резать торт следующим хитрым образом. Каждый раз он будет выбирать три последовательные вершины многоугольника и одиночным разрезом отрезать получившийся треугольный кусок торта очередному гостю. В результате после N разрезов у Васи останется его собственный кусок, также имеющий форму треугольника.
Однако Вася очень любит новогодние торты, поэтому он решил таким образом отрезать от торта куски, чтобы его собственный последний кусок был максимального размера. Для этого он быстренько составил программу, которая посчитала площадь Васиного куска торта. А сможете ли вы написать такую программу?
Входные данные
В первой строке входного файла записано целое число N (0 ≤ N ≤ 50). Каждая из следующих (N+3) строк содержит два целых числа X и Y, по модулю не превосходящих 10000 – координаты вершин многоугольника в некоторой декартовой системе координат в порядке обхода по часовой стрелке.
Выходные данные
В единственную строку выходного файла выведите максимально возможную площадь Васиного куска торта. Ответ будет засчитан, если он равен правильному результату с точностью до 0.001.
Пример
| cake.in | cake.out |
|---|---|
|
|