Классический миф: Супергерой из Плоскоземелья
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, а окончательные ответы отображаться в десятичной нотации с фиксированной точкой и округляться до четырех десятичных знаков точности, как показано в примере входных и выходных данных.