Editorial for COCI '16 Contest 7 #5 Paralelogrami


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

If all points are collinear, then we obviously can't make a single move, so the solution does not exist.

First, notice that the operation of mapping the point C over points A and B can be written in a simple algebraic form, instead of a geometric one:

(C_x, C_y) is mapped over (A_x, A_y) and (B_x, B_y) into point (A_x+B_x-C_x, A_y+B_y-C_y)

Let's assume that there are 3 non-collinear points. We will prove that we can bring them into a part of the plane that holds points with x and y coordinates being at least 5. Then, each of the remaining N-3 points can be mapped into the first quadrant using exactly one operation. From the upper equation, it is clear why this newly created point is located in the first quadrant.

If there are 3 non-collinear points, let's prove that we can bring them in the aforementioned part of the plane. Let the 3 points be A, B, C and let D be a point obtained by a single mapping, for example of point C over AB.

Now, we have a parallelogram ACBD. Notice that, by using this parallelogram, we can pave the plane in the way shown in the image (by translating that parallelogram).

Also, notice that, for each of the parallelograms used for paving the plane, there is a series of operations after which our 3 points become 3 vertices of that parallelogram.

Since the parallelogram paves the entire plane, it also paves the quadrant that holds the points with x and y coordinates being at least 5. Therefore, there must exist a parallelogram that is entirely located within that quadrant and a series of operations after which our points become 3 vertices of that quadrant.

One remaining question is how many moves this algorithm takes. There are at least 2 algorithms that find a sufficiently small number of moves:

  • We run a BFS algorithm where the state is the 3 current points, and the transition is the application of one of the 3 possible operations in each state. We limit the BFS not to spread into triangles that do not intersect with the part of the plane [-10, \infty] \times [-10, \infty], since we know that the solution exists even without spreading into such triangles. The coordinates are small, so we use a brute force approach to see that, worst case scenario, we need less than 1200 operations to get to the required part of the plane, which is sufficient.
  • We denote with A, B, C the vertices of our triangle. Notice that there exists a vertex of the triangle, without loss of generality, let's say that it is vertex C, such that the part of the plane bounded by rays CA and CB intersects with the part of the plane where we want to bring the 3 points. We map point C over line AB. We leave the proof of correctness of this algorithm as an exercise for the reader.

Comments

There are no comments at the moment.