BACKTPOL - Back To The Polygon

no tags 

A simple polygon is a polygon that does not overlap with itself. A diagonal of a simple polygon
is a segment within the polygon that connects two non-consecutive vertices. A triangulation
of a simple polygon of N edges is the drawing of exactly N − 3 diagonals that do not touch
each other anywhere, with the possible exception of their endpoints. A triangulation divides
the polygon in exactly N − 2 triangles that do not overlap and only touch each other along
their edges.

In this problem, you are given the triangulation of a simple polygon, which means, the set of
triangles in which a polygon was divided. From them, you need to reconstruct the original
polygon.

Input

The input contains several test cases, each one described in several lines. The first line of each
test case contains an integer N (3 ≤ N ≤ 500), the number of edges of the original polygon.
Each of the next N − 2 lines describes one triangle in the triangulation of the polygon. Each
triangle is given by six integers X1 , Y1 , X2 , Y2 , X3 and Y3 separated by single spaces, where Xi
and Yi are the coordinates in the XY plane of the i-th vertex of the triangle (−1000 ≤ Xi , Yi ≤
1000). The triangles and their vertices are not given in any specific order. The last line of the
input contains a single −1 and should not be processed as a test case.

Output

For each test case output a single line with 2N integers separated by single spaces. These
integers must represent the coordinates in the XY plane of the vertices of the original polygon,
in clockwise order. To make the output unique, the first vertex to be listed is the one with the
smallest X coordinate, and if there are many of those, the one with the smallest Y coordinate
among them.

Example

Input:
5
0 0 10 9 10 0
10 9 0 9 0 0
10 9 0 9 5 13
3
0 1 1 1 1 0
10
-1 -2 2 -2 2 -1
-1 -2 0 -1 -2 3
-2 3 2 3 1 2
0 -1 2 1 1 2
-1 -2 2 -1 0 -1
2 1 0 -1 2 0
2 3 2 2 1 2
0 -1 -2 3 1 2
-1
Output:
0 0 0 9 5 13 10 9 10 0
0 1 1 1 1 0
-2 3 2 3 2 2 1 2 2 1 2 0 0 -1 2 -1 2 -2 -1 -2


Added by:Pablo Ariel Heiber
Date:2010-08-13
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2007