Problem K
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.

\includegraphics[width=0.4\textwidth ]{sample_sculpture}
Figure 1: Sample input sculpture with optimal (lowest total cost) support struts.


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
0 0
0 5
5 2
2 0
1 1

Please log in to submit a solution to this problem

Log in