eolymp
bolt
Try our new interface for solving problems

M-gon

Given \textbf{N} distinct points on the plane and a positive integer \textbf{M}. Required to find the maximum area nonsingular \textbf{M}-gon without self-intersections and self-tangencies, whose vertices are some of the given \textbf{N} points. \InputFile In the first line of input contains space-separated two numbers: \textbf{M} and \textbf{N} (\textbf{3} ≤ \textbf{M}, \textbf{N} ≤ \textbf{10}). In the next \textbf{N} lines through space are \textbf{N} pairs of real numbers: \textbf{x_1}, \textbf{y_1}, \textbf{x_2}, \textbf{y_2}, …, \textbf{x_N}, \textbf{y_N} -- coordinates of points on the plane. \OutputFile In the first line of the output file you want to display the desired area of the \textbf{M}-gon, with an accuracy of one digit after the decimal point. If neither \textbf{M}-gon with these properties can not be constructed, then the output file should contain only the number \textbf{0}.
Time limit 1 second
Memory limit 64 MiB
Input example #1
3 4
0 0
0 1
1 0
1 1
Output example #1
0.5