poligon

A convex polygon with n vertices is given via the coordinates of the vertices, which are given in clockwise order. A point S from the plain of the polygon is the center of symmetry, if the symmetric of any polygon point as compared to S belongs to the polygon. One of the property of convex polygons with a center of symmetry is that they can be decomposed into parallelograms.

Task

Verify whether the given polygon has a center of symmetry. If positive, divide the polygon into parallelograms.

Input Data

Input file poligon.in contains on line one a non-zero positive integer k, which represents the number of tests, followed by k data groups, one group for each test. A data group contains on a line the number n, and on the following n lines the coordinates of the polygon's vertices in the following format:
n
x₁ y₁
x₂ y₂
…
x_n y_n

Output Data

Output file poligon.out will contain the answer to the k tests of the input file. For each test the positive integer h, representing the number of parallelograms from the decomposition will be written on a line, followed by h lines with the coordinates of the vertices of the parallelograms resulting from the decomposition, in format:
h
px₁₁ py₁₁ px₂₁ py₂₁ px₃₁ py₃₁ px₄₁ py₄₁
px₁₂ py₁₂ px₂₂ py₂₂ px₃₂ py₃₂ px₄₂ py₄₂
…
px_1h py_1h px_2h py_2h px_3h py_3h px_4h py_4h
if there is a center of symmetry, otherwise only digit 0 will be written.
A parallelogram is described via the coordinates of its vertices in clockwise order (abscise ordinate).

Constraints and Statements

• 1 <= k <= 5
• 4 <= n <= 50
• The coordinates of the polygon's vertices are integers in the [-2000, 2000] interval.
• If two parallelograms with disjunct interiors have a common side and two other continuing sides (like parallelograms ABED and BCFE in the following image) a single parallelogram will be displayed (in the image that would be ACFD).
  
  

Time limit: 0.1 seconds/test

prof. Doru Popescu Anastasiu
"Radu Greceanu" National College Slatina
Contact:dopopan@yahoo.com