eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Площа між зовнішньою та внутрішньою оболонками

Площа між зовнішньою та внутрішньою оболонками

Задано множину \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} десятковими знаками.
Ліміт часу 5 секунд
Ліміт використання пам'яті 128 MiB
Вхідні дані #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
Джерело ACM ICM Philippines Multi-Provincial Programming Contest 2013