Опуклі оболонки (ConvexHulls)
Опукла оболонка множини точок - опуклий багатокутник з найменшою площею, що містить усю множину точок.
Вам дано n точок на площині. Довільним чином можна вибрати і видалити одну із заданих точок, після чого побудувати опуклу оболонку решти. Очевидно, що видаляючи різні точки, ви будете отримувати різні опуклі оболонки.
Припустимо, Ви по черзі видаляєте точки заданої множини і будуєте опуклі оболонки (видаляючи чергову точку, попередньо видалену Ви повертаєте назад). Зробивши вказану дію для кожної точки, Ви отримаєте n опуклих оболонок (деякі з яких можуть співпадати). Запишемо набір чисел, що дорівнюють кількості вершин в кожній з отриманих опуклих оболонок. Знайдіть середнє арифметичне даного набору чисел.
Вважати, що якщо опукла оболонка є відрізком, то в ній дві вершини. Якщо ж вона є невиродженим багатокутником, то всі кути при вершинах строго менше π.
Формат введення-виведення:
Спочатку програма ConvexHulls читає з клавіатури (стандартного пристрою введення) число n (3 ⩽ n ⩽ 2 · 105) - кількість точок множини. Далі у наступному рядку читаються пари цілих чисел, що не перевищують по модулю 109 - координати точок. Гарантується, що жодні дві точки не співпадають.
Програма ConvexHulls виводить на екран (стандартний пристрій виведення) два числа через пробіл p q, де p, q – цілі невід'ємні числа.
Приклад вхідних та вихідних даних
| Введення | Виведення |
| 5 0 0 0 4 4 0 3 3 4 4 |
17 5 |