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