Decomposing a Point Set into a Layered Translation Structure

Given a set (a) of points on the plane, you are to find a triple ((b,x,z)) satisfying the following conditions in (\mathbb{R}^2):

1. There exists a positive integer (z) such that [ a = b \cup (b+x) \cup (b+2x) \cup \cdots \cup (b+zx), ] where for any set (S) and vector (x), (S+x = {p+x:; p \in S}).

2. Among all valid triples, the one you output must have the maximum possible (z) (denote it by (z_0)).

3. The base point set (b) (which we denote by (b_0)) must satisfy the following geometric properties:

   • Any three distinct points in (b_0) are non‐collinear.
   • Any four distinct points in (b_0) do not form a trapezoid or a parallelogram.
   • For every positive integer (y), the translated set (b_0 + y x_0) is disjoint from (b_0); that is, (b_0 \cap (b_0+yx_0) = \varnothing) for all (y \ge 1).

Your task is: Given the input set (a), output any valid triple ((b_0, x_0, z_0)) that meets all the above requirements. Notice that (z_0) must be chosen maximum among all such decompositions.

Input Format:

• The first line contains an integer \(n\) denoting the number of points in \(a\).
• Each of the following \(n\) lines contains two integers representing the coordinates of a point.

Output Format:

• On the first line, output three space‐separated integers: \(z_0\) (the maximum layer index), followed by the two components of the chosen translation vector \(x_0\) (i.e. \(x_{0x}\) and \(x_{0y}\)).
• On the second line, output an integer \(m\) denoting the number of points in the base set \(b_0\).
• Then output \(m\) lines, each with two integers representing the coordinates of a point in \(b_0\) (order them in lexicographical order based on the coordinates).

Note: It is guaranteed that the input point set (a) has a valid decomposition of the form described above. In case there are several valid answers, any one is acceptable provided that (z_0) is maximum.

Hint: A common method is to try to "peel off" layers from (a). For a fixed translation vector candidate (x), the base layer can be determined as all points (p) in (a) such that (p-x \notin a). Then, verify if layering (b, b+x, b+2x, \dots, b+zx) exactly recovers (a) and choose the candidate which gives the maximum (z).

inputFormat

The input begins with an integer n (1 ≤ n ≤ 10⁵), the number of points in the set a. Each of the next n lines contains two integers, representing the x and y coordinates of a distinct point. It is guaranteed that the points form a valid layered structure as described in the problem.

outputFormat

On the first line, output three space-separated integers: the maximum integer z₀ and the two components of the translation vector x₀ (i.e. x_0x and x_0y). On the second line, output an integer m denoting the number of points in the base set b₀. Each of the next m lines should contain two integers representing a point in b₀ (listed in lexicographical order).

sample

3
0 0
1 0
2 0

2 1 0
1
0 0