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