eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

A Classic Myth: Flatland Superhero

A Classic Myth: Flatland Superhero

Flatland needs a superhero! Recently swarms of killer ants have been invading Flatland, and nobody in Flatland can figure out how to stop these dastardly denizens. Fortunately, you (as a higher dimensional being) have the opportunity to become a superhero in the eyes of the Flatland citizens! Your job is to “freeze” swarms of ants using parallelograms. You will do this by writing a program that finds a minimal area enclosing parallelogram for each swarm of ants. Once a minimal area parallelogram is placed around the ant swarm, they are effectively frozen in place and can no longer inflict terror on planar inhabitants. \includegraphics{https://static.e-olymp.com/content/f6/f6dadd8cd4a5bba150b0d5e2a3590d261baf2520.jpg} Figure 1: A Frozen Swarm of Ants in Flatland \InputFile The input will consist of the following: \begin{itemize} \item A line containing a single integer, \textbf{s} (\textbf{1} ≤ \textbf{s} ≤ \textbf{20}), which denotes the number of killer antswarms. \item Each swarm will start with a single line containing an integer, \textbf{n} (\textbf{4} ≤ \textbf{n} ≤ \textbf{1000}), whichindicates the number of killer ants in the swarm. \item The next \textbf{n} lines contain the current location of each killer ant in the swarm. \item Each killer ant is represented by a single line containing two numbers: \textbf{x} (\textbf{−1000} ≤ \textbf{x} ≤ \textbf{1000})and \textbf{y} (\textbf{−1000} ≤ \textbf{y} ≤ \textbf{1000}) separated by a space. \item Only one killer ant will occupy each (\textbf{x}, \textbf{y}) location in a particular swarm. Each swarm shouldbe dealt with independently of other swarms. \item All data inputs are in fixed point decimal format with four digits after the decimal (e.g.,\textbf{dddd.dddd}). \item There may be multiple parallelograms with the same minimum area. \end{itemize} \OutputFile For each swarm, your algorithm should output a line that contains "\textbf{Swarm i Parallelogram Area: }", where \textbf{i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{s}) is the swarm number, followed by the minimum area (rounded to \textbf{4} decimal digits and using fixed point format) of an enclosing parallelogram for that swarm. All computations should be done using \textbf{64} bit IEEE floating point numbers, and the final answers displayed in fixed point decimal notation and rounded to four decimal digits of accuracy as shown in the sample input and output.
Лимит времени 10 секунд
Лимит использования памяти 256 MiB
Входные данные #1
2
6
0.0000 0.0000
-0.5000 -0.5000
-1.0000 0.0000
-0.7000 -7.0000
-1.0000 -1.0000
0.0000 -1.0000
5
2.0000 2.0000
0.0000 0.0000
0.5000 2.0000
1.0000 1.0000
1.5000 0.0000
Выходные данные #1
Swarm 1 Parallelogram Area: 7.0000
Swarm 2 Parallelogram Area: 3.0000
Источник ACM ICPC 2011 Pacific Northwest Region Programming Contest