Editorial for COCI '16 Contest 7 #5 Paralelogrami
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 over points and can be written in a simple algebraic form, instead of a geometric one:
is mapped over and into point
Let's assume that there are non-collinear points. We will prove that we can bring them into a part of the plane that holds points with and coordinates being at least . Then, each of the remaining 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 non-collinear points, let's prove that we can bring them in the aforementioned part of the plane. Let the points be and let be a point obtained by a single mapping, for example of point over .
Now, we have a parallelogram . 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 points become vertices of that parallelogram.
Since the parallelogram paves the entire plane, it also paves the quadrant that holds the points with and coordinates being at least . Therefore, there must exist a parallelogram that is entirely located within that quadrant and a series of operations after which our points become vertices of that quadrant.
One remaining question is how many moves this algorithm takes. There are at least algorithms that find a sufficiently small number of moves:
- We run a BFS algorithm where the state is the current points, and the transition is the application of one of the possible operations in each state. We limit the BFS not to spread into triangles that do not intersect with the part of the plane , 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 operations to get to the required part of the plane, which is sufficient.
- We denote with 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 , such that the part of the plane bounded by rays and intersects with the part of the plane where we want to bring the points. We map point over line . We leave the proof of correctness of this algorithm as an exercise for the reader.
Comments