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

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

5 секунд

128 мегабайтів

Середня

Дано множину $S$ з $N$ точок на площині:

S = {(x_{0}, y_{0}), (x_{1}, y_{1}), \dots, (x_{N - 1}, y_{N - 1})},

S = \{ (x_0, y_0),\ (x_1, y_1),\ \ldots,\ (x_{N-1}, y_{N-1}) \},

Зовнішня оболонка $H o$ множини $S$ — це опукла оболонка $S$ : підмножина точок $S$ , які, з'єднані відрізками, утворюють опуклий багатокутник $P$ найменшої площі, що містить усі точки $S$ всередині чи на границі $P$ . Точки $S$ , що лежать на $P$ , але не є вершинами $P$ , не входять до опуклої оболонки.

Внутрішня оболонка $H i$ множини $S$ визначається як опукла оболонка множини $S - H o$ S - Ho: потрібно видалити з $S$ усі точки зовнішньої оболонки $H o$ , отримати множину $S - H o$ S - Ho і побудувати її опуклу оболонку — це й буде $H i$ .

Наприклад, $S$ складається з $8$ точок: $A (2.0, 5.0)$ , $B (2.0, 4.0)$ B(2.0, 4.0), $C (2.0, 2.0)$ C(2.0, 2.0), $D (1.0, 1.0)$ D(1.0, 1.0), $E (4.0, 1.0)$ E(4.0, 1.0), $F (0.0, 0.0)$ F(0.0, 0.0), $G (3.0, 0.0)$ та $H (5.0, 0.0)$ H(5.0, 0.0). Зовнішня оболонка $H o = {F, H, A, F}$ Ho = \{ F, H, A, F \}. Після видалення $H o$ з $S$ , $S - H o = {B, C, D, E, G}$ S - Ho = \{ B, C, D, E, G \}. Внутрішня оболонка $H i = {D, G, E, B, D}$ Hi = \{ D, G, E, B, D \}. Площа всередині $H o$ — $12.5$ , всередині $H i$ — $6.0$ , різниця: $12.5 - 6.0 = 6.5$ 12.5 - 6.0 = 6.5.

Дано множину $S$ з $N$ точок. Потрібно обчислити площу між зовнішньою оболонкою $H o$ та внутрішньою оболонкою $H i$ цієї множини.

Вхідні дані

Вхід складається з декількох наборів. Перший рядок кожного набору містить ідентифікатор та ціле число $N$ ( $N \leq 1000$ N \leq 1000). Наступні $N$ рядків містять координати $x$ і $y$ (через пробіл) точки; кожне $x$ та $y$ — дійсні числа, $∣ x ∣, ∣ y ∣ \leq 100.0$ |x|,|y| \leq 100.0. Наступний набір іде одразу після попереднього. Рядок з ідентифікатором "ZZ" і $N = 0$ N = 0 означає кінець вводу.

Вихідні дані

Для кожного набору даних виведіть рядок:

ProblemID id: area

де $i d$ — ідентифікатор задачі з вхідних даних, $a r e a$ — обчислена площа між $H o$ та $H i$ .

Площу виводьте точно з $4$ знаками після десяткової крапки.

Приклади

Приклад 1