Задачі
Площа між зовнішньою та внутрішньою оболонками
Площа між зовнішньою та внутрішньою оболонками
Задано множину \textbf{S} з \textbf{N} точок на площині, а саме \textbf{S = \{(x\[0\], y\[0\]), (x\[1\], y\[1\]), ..., (x\[N-1\], y\[N-1\])\}}. Зовнішня опукла оболонка \textbf{Ho }множини \textbf{S} - це сама опукла оболонка \textbf{S}. Це така підмножина точок \textbf{S}, які якщо з'єднати відрізками, то утворюється опуклий многокутник \textbf{P} найменшої площі такий, що усі точки \textbf{S} лежать всередині \textbf{P} або на \textbf{P}. Точки з \textbf{S}, які лежать на \textbf{P}, але не є вершинами \textbf{P}, не є частино опуклої оболонки. Внутрішняя опукла оболона \textbf{Hi} множини \textbf{S} отримується побудовою опуклої оболонки множини \textbf{S--Ho}. Тобто видаленням з множини \textbf{S} усіх точок, які належать зовнішній опуклій оболонці \textbf{Ho}, внаслідок чого отримується множина \textbf{(S--Ho)}. Внутрішня опукла оболона \textbf{Hi} будується як оыпукла оболонка \textbf{(S--Ho)}.
\includegraphics{https://static.e-olymp.com/content/fb/fba50093355eeed09781c310ce218aa3bb0fca9f.jpg}
Наприклад, нехай множина \textbf{S} складається з \textbf{8} точок \textbf{A(2.0, 5.0)}, \textbf{B(2.0, 4.0)}, \textbf{C(2.0, 2.0)}, \textbf{D(1.0, 1.0)}, \textbf{E(4.0, 1.0)}, \textbf{F(0.0, 0.0)}, \textbf{G(3.0, 0.0)} та \textbf{H(5.0, 0.0)}. Зовнішню опуклу оболонку \textbf{Ho} множини \textbf{S} утворює множина \textbf{Ho = \{F, H, A, F\}}. Якщо видалити \textbf{Ho} з \textbf{S}, то отримаємо \textbf{S--Ho = \{B, C, D, E, G\}}. Внутрішня опукла оболонка \textbf{Hi }множини \textbf{S} обчислюється як опукла оболонка \textbf{S--Ho}, тобто \textbf{Hi = \{D, G, E, B, D\}}. Площа всередині \textbf{Ho} дорівнює \textbf{area(Ho) = 12.5}. Площа всередині \textbf{Hi} дорівнює \textbf{area(Hi) = 6.0}. Площа, розміщена між зовнішньою опуклою оболонкою \textbf{Ho} та внутрішньою \textbf{Hi}, дорівнює \textbf{12.5 -- 6.0 = 6.5}.
Напишіть програму, яка за заданою множиною \textbf{S} із \textbf{N} точок обчислить площу між зовнішньою опуклою оболонкою \textbf{Ho} множини \textbf{S} та внутрішньою опуклою оболонкой \textbf{Hi} множини \textbf{S}.
\InputFile
Вхідні дані складаються з декількох тестів. Перший рядок кожного тесту містить \textbf{problemID} та значення \textbf{N}, яке не перевищує \textbf{1000}. Наступні \textbf{N} рядків містять значення \textbf{x}- та \textbf{y}-координат (відокремлені пропуском) точки, кожна точка задається у одному рядку. Кожна координата \textbf{x} або \textbf{y} є дійсним числом, не більшим \textbf{100.0} по модулю. Тести йдуть безпосередньо один за одним. Рядок з \textbf{problemID} рівним "\textbf{ZZ}" і значенням \textbf{N} = \textbf{0} вказує на кінець вхідних даних.
\OutputFile
Для кожного тесту вивести рядок виду "\textbf{ProblemID id: area}", де \textbf{id} зберігає \textbf{problemID} задане у вхідних даних, \textbf{area} - площа між обчисленими значеннями площ зовнішньої опуклої оболонки \textbf{Ho} та внутрішньої \textbf{Hi}.
Площу потрібно виводити з \textbf{4} десятковими знаками.
Вхідні дані #1
A1 8 2.0 5.0 2.0 4.0 2.0 2.0 1.0 1.0 4.0 1.0 0.0 0.0 3.0 0.0 5.0 0.0 A2 11 1.0 5.0 5.0 5.0 2.0 4.0 3.0 4.0 2.0 3.0 2.0 2.0 3.0 2.0 1.0 1.0 4.0 1.0 0.0 0.0 4.0 0.0 ZZ 0
Вихідні дані #1
ProblemID A1: 6.5000 ProblemID A2: 14.0000