Гра з многокутником

Обмеження: 2 сек., 256 МіБ

Зеник і Марічка досвідчені ковзанярі. Їм не хочеться просто кататися, тому вони придумали таку гру.

Перед початком гри Зеник віртуозно рисує ковзанами на льоду опуклий \(n\)-кутник.

Коли многокутник готовий, гравці починають ходити по черзі. Марічка ходить першою.

За один хід гравець може вибрати діагональ многокутника та проїхати вздовж неї, прорізаючи лід. Діагональ розділить многокутник на два менші многокутники. Тоді гравець вибирає одну з двох частин, на якій буде продовжуватися гра. На цьому хід закінчується.

Гра завершується, коли залишився трикутник.

Марічка хоче максимізувати площу трикутника, що залишиться, Зеник — мінімізувати.

Яка буде площа при оптимальній грі обох гравців?

Вхідні дані

У першому рядку записано ціле число \(n\) — кількість вершин многокутника.

У наступних \(n\) рядках задано по два цілих числа \(x_i\), \(y_i\) — координати вершин многокутника в порядку обходу проти годинникової стрілки.

Вихідні дані

Виведіть ціле число — подвоєну площу трикутника, що залишиться після завершення гри.

Можна довести, що подвоєна площа трикутника з вершинами в цілочисельних точках є цілою.

Обмеження

\(4 \le n \le 10^5\),

\(|x_i|, |y_i| \le 10^9\),

жодні три вершини многокутника не лежать на одній прямій.

7 балів: \(n \le 15\);

8 балів: \(n \le 10^3\);

10 балів: без додаткових обмежень.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 0 0 7 4 3 11 -4 7	65

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
20 -20 5 -20 1 -19 -3 -17 -7 -15 -9 -13 -10 -11 -10 5 -8 12 -7 15 -6 17 -4 18 -1 18 3 17 6 15 8 12 9 8 9 -5 8 -14 7 -19 6	4

Примітки

У першому прикладі після першого ходу Марічки гра завершиться. Незалежно від того, яку діагональ вона вибере, квадрат поділиться на два рівні трикутники.

У другому прикладі один з можливих сценаріїв такий. Марічка прорізає діагональ між вершинами \((-15, -9)\) і \((5, -8)\) (фіолетову) та залишає для гри верхню частину. Зеник проводить діагональ між вершинами \((-20, 5)\) і \((-19, -3)\) (зелену) та залишає трикутник. На цьому гра закінчується.