Площадь между внешней и внутренней оболочками
Задано множество 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 десятичными знаками.