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