Класичний міф: Супергерой з Плоского світу#3572
Flatland потребує супергероя! Нещодавно рої мурах-вбивць почали вторгатися у Flatland, і ніхто не знає, як зупинити цих підступних істот. На щастя, ви (як істота вищого виміру) можете стати супергероєм для мешканців Flatland! Ваше завдання — «заморозити» рої мурах за допомогою паралелограмів. Ви зробите це, написавши програму, яка знаходить мінімальну площу охоплюючого паралелограма для кожного рою мурах. Як тільки паралелограм мінімальної площі розміщено навколо рою мурах, вони ефективно заморожуються на місці і більше не можуть наводити жах на мешканців площини.
Рисунок 1: Заморожений рій мурах у Flatland
Вхідні дані складаються з наступного:
Рядок, що містить одне ціле число, (1 \leq s \leq 20), яке позначає кількість роїв мурах-вбивць.
Кожен рій починається з одного рядка, що містить ціле число, (4 \leq n \leq 1000), яке вказує на кількість мурах-вбивць у рої.
Наступні рядків містять поточне місцезнаходження кожної мурахи-вбивці в рої.
Кожна мураха-вбивця представлена одним рядком, що містить два числа: (-1000 \leq x \leq 1000) і (-1000 \leq y \leq 1000), розділені пробілом.
Лише одна мураха-вбивця займатиме кожне місце (, ) в конкретному рої. Кожен рій слід обробляти незалежно від інших роїв.
Усі вхідні дані подані у фіксованому десятковому форматі з чотирма цифрами після коми (наприклад, dddd.dddd).
Може існувати кілька паралелограмів з однаковою мінімальною площею.
Для кожного рою ваш алгоритм повинен вивести рядок, що містить "Swarm Parallelogram Area: ", де (1 \leq i \leq s) — це номер рою, за яким слідує мінімальна площа (округлена до десяткових цифр і у фіксованому десятковому форматі) охоплюючого паралелограма для цього рою. Усі обчислення повинні виконуватися з використанням -бітних чисел з плаваючою комою IEEE, а остаточні відповіді відображатися у фіксованій десятковій нотації та округлятися до чотирьох десяткових знаків точності, як показано у прикладі вхідних та вихідних даних.
Приклад 1