Problem B
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
![\includegraphics[width=0.6\textwidth ]{sample}](/problems/cuttingcorners/file/statement/en/img-0001.png)
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
Input
Input consists of up to
Output
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 0 |
4 0 3 4 7 7 6 4 0 3 0 0 3 5 6 0 |