OrthogonalProjections

If point X lies on the line L, the orthogonal projection of X onto L is X itself. Otherwise, the orthogonal projection of X onto L is the unique point Y on L such that XY is orthogonal to L.

Suppose you are given a finite sequence S of points in the plane. Two lines L1 and L2 are equivalent if the orthogonal projections of points of S onto L1 are in the same order as the projections of points of S onto L2.

For example, suppose the points in S are S[0]=(0,0), S[1]=(0,1), and S[2]=(1,2). The figure below shows two blue lines that are equivalent: the points of S projected onto each of them lie in the order 0, 1, 2.

The second figure below shows the same sequence of points and two other lines. On the red line the projections of 0 and 1 coincide, so the order is 0+1, 2. The green line has the projections in order 1, 0, 2. Thus, these lines represent two new equivalence classes.

(Note that lines don't have direction. A line on which the projections lie in the order 1, 0, 2 is the same as a line on which they are in the order 2, 0, 1.)

For a fixed sequence S of points in the plane let g(S) denote the number of equivalence classes among lines in that plane.

You are given a int n. If there is no S such that g(S) = n, return an empty int[]. Otherwise, find any such S with the following additional properties:

• S must contain between 1 and 500 points, inclusive.
• The points in S must be distinct.
• The coordinates of each point in S must be integers between 0 and 10^9, inclusive.

Then, return the following int[]: { S[0].x, S[0].y, S[1].x, S[1].y, ... }.