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