Problem A
Cutting Corners

You work for a day care center. You have a big tub of convex polygons that you are going to let the children play with. However, you notice that some of the shapes have pointy corners. You decide to make them safer by cutting off the most pointy corners as illustrated below. You choose the corner that has the most acute angle. You then cut straight across from its two neighboring corners. In the following figure, the $cde$ angle is the sharpest. You cut it off by cutting straight from $c$ to $e$. You then throw away the $d$ corner you just cut off and keep the $abce$ shape.

\includegraphics[width=0.6\textwidth ]{sample}

You repeatedly cut off the sharpest corner until you are left with a triangle or until cutting off the most pointy corner produces an even more pointy corner. For example, after cutting off the $d$ corner above, angle $cea$ is the sharpest. However, if you cut it off, you would just produce even sharper angles. Thus, you should stop after just one cut. For some shapes, you may not be able to cut off any corners because they either start as a triangle or are not improved by cutting off the sharpest corner. There will never be more than one sharpest corner that is also cuttable.


Input consists of up to $100$ shape descriptions. Each shape starts with a number $1 \le n \le 20$ giving the number of corners. This is followed by a sequence of $n$ pairs of integers, each pair giving the $X \; Y$ location of a corner. All coordinates are in the range $[0, 15\, 000]$. Corners are given in clockwise order around the perimeter of each shape. Every shape has at least three corners and no two corners are coincident. The end of input is marked with a value of zero for $n$.


For each shape, print a line giving what the shape looks like after you are done cutting it. Use the same format as the input and print the corners in the same order they were given in the input.

Sample Input 1 Sample Output 1
5 0 3 4 7 7 6 10 1 4 0
5 0 0 3 5 6 7 9 8 6 0
4 0 3 4 7 7 6 4 0
3 0 0 3 5 6 0

Please log in to submit a solution to this problem

Log in