Jungle Kingdom Laws#12831

Jungle Kingdom Laws

1 секунда
512 мегабайтів
Складна

Королівство Джунглів можна подати як опуклий многокутник з вершинами. Король Лев вирішив поділити королівство на два райони та віддати ці райони у керування двох його друзів.

Закони королівства дозволяють таке розділення тільки якщо країну розділено якоюсь діагоналлю (відрізком, що з'єднує дві вершини). Король хоче зробити різницю у площі районів якомога меншою. Маючи координати вершин королівства, допоможіть йому знайти ту різницю.

Вхідні дані

Перший рядок містить одне ціле (1 \leq N \leq 60000) — кількість вершин у многокутнику, що задає королівство. Кожен з наступних рядків містить два цілих числа x_i та y_i (0 \leq x_i, y_i \leq 10^9) — координати наступної вершини у многокутнику. Вершини задані проти годинникової стрілки. Ви можете вважати що заданий многокутник є строго опуклим без трьох вершин на одній прямій.

Вихідні дані

Надрукуйте одне невід'ємне число — мінімальне абсолютне значення різниці площ з абсолютною або відносною похибкою 10^{-9} або краще.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading