Structural Integrity

The Makers’ Association of Pristine Sculptures (MAPS) has come up with designs for some new sculptures. However, none of the designs meet the necessary safety standards.

Each initial sculpture design can be modelled as a simple
polygon. To make a design safe, it must be augmented with
support struts. Each strut can be modelled as a line segment
between two vertices of a polygon. Specifically, for an
$n$-sided polygon
sculpture design there must be $n-3$ support strut line segments
between $n-3$ distinct
pairs of vertices such that, with the exception of the
endpoints of the struts, each support strut lies entirely in
the interior of the polygon. The support struts may share
endpoints with one another, but they may *not* intersect
one another at any other point.

MAPS wants to make make its designs safe, but its members do not want to spend more money than is necessary to meet the safety standards. The cost of a support strut is equal to the square of its length. The cost of a safe design is the sum of the costs of the struts used to make the design safe. Help MAPS by finding the smallest cost to make each of its designs safe.

The input starts with a line containing an integer, $n$ $(4\leq n\leq 200)$, specifying the number of vertices of the polygon modelling a sculpture. This is followed by $n$ lines, each containing two space-separated integers, $x$ and $y$ $(|x|,|y|\leq 10^4)$, that give the coordinates $(x,y)$ of the vertices of the polygon in clockwise order. The polygon is simple, i.e., its vertices are distinct and no two edges of the polygon intersect or touch, except that consecutive edges touch at their common vertex. In addition, no three consecutive vertices are collinear.

Output a single positive integer, the minimum cost required
to make the design safe. If it is not possible to place
$n-3$ struts as described
above, output “`impossible`”
instead.

Sample Input 1 | Sample Output 1 |
---|---|

5 0 0 0 5 5 2 2 0 1 1 |
34 |