Offset Polygons
One very common geometrical operation in polygon manipulation is finding offset polygons. An offset polygon is obtained by tracing lines, parallel to the original polygon edges, maintaining a given offset distance from them. Here, we are only interested in exterior offset polygons like the one shown in Figure 1, printed in dotted lines. In these circumstances, the offset polygon can be found "to the left" of each original edge, when circulating in the clockwise direction.
Figure
1 - An exterior offset polygon obtained with an offset value of 1.
Given an offset value and a sequence of vertices coordinates
defining a clockwise closed polygon, the problem is to obtain the correspondent
exterior offset polygon. The result must be given as a sequence of vertices
coordinates, also in the clockwise direction.
To simplify the problem, the original polygon is guaranteed to be
closed, convex, and limited to 8 vertices. Two consecutive edges are never collinear.
The first line of the input contains the offset value (float format). The second line contains the number of vertices of the original polygon N (integer format). Each one of the following N lines contains two float values, separated by one or more spaces, representing the X and Y coordinates of a vertex. The sequence of vertices is guaranteed to be in the clockwise direction.
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
The output must follow the input format (except for the offset value) to represent the exterior offset polygon. The first vertex listed must correspond to the first vertex given.
Sample Input
1
1.0
5
10.0 5.0
10.0 3.0
3.0 3.0
3.0 6.0
5.0 8.0
Sample Output
5
11.000 5.566
11.000 2.000
2.000 2.000
2.000 6.414
4.845 9.259