Plane Tiling
Contest: 2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules)
Difficulty rating: 2500
Tags: geometry, implementation, math

You are given five integers $$$n$$$, $$$dx_1$$$, $$$dy_1$$$, $$$dx_2$$$ and $$$dy_2$$$. You have to select $$$n$$$ distinct pairs of integers $$$(x_i, y_i)$$$ in such a way that, for every possible pair of integers $$$(x, y)$$$, there exists exactly one triple of integers $$$(a, b, i)$$$ meeting the following constraints:

$$$ \begin{cases} x \, = \, x_i + a \cdot dx_1 + b \cdot dx_2, \\ y \, = \, y_i + a \cdot dy_1 + b \cdot dy_2. \end{cases} $$$

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line contains two integers $$$dx_1$$$ and $$$dy_1$$$ ($$$-10^6 \le dx_1, dy_1 \le 10^6$$$).

The third line contains two integers $$$dx_2$$$ and $$$dy_2$$$ ($$$-10^6 \le dx_2, dy_2 \le 10^6$$$).

Output format:
If it is impossible to correctly select $$$n$$$ pairs of integers, print NO.

Otherwise, print YES in the first line, and then $$$n$$$ lines, the $$$i$$$-th of which contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$).

If there are multiple solutions, print any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Example input:
4
2 0
0 2

Example output:
YES
0 0
0 1
1 0
1 1

Example input:
5
2 6
1 5

Example output:
NO

Editorial:
One of the solutions is to consider an infinite 2 dimensional plane and draw a grid with lines parallel to vectors ($$$dx_1$$$, $$$dy_1$$$) and ($$$dx_2$$$, $$$dy_2$$$). By doing so we will get a tiling of the plane with parallelepipeds, one of them will have corners at ($$$0$$$, $$$0$$$), ($$$dx_1$$$, $$$dy_1$$$), ($$$dx_1 + dx_2$$$, $$$dy_1 + dy_2$$$), ($$$dx_2$$$, $$$dy_2$$$).
All the parallelepipeds are same shape and all of them can be represented by translating one of them by vector ($$$a \cdot dx_1 + b \cdot dx_2$$$, $$$a \cdot dy_1 + b \cdot dy_2$$$), where $$$a$$$ and $$$b$$$ are all possible integer pairs. Thus, if we "rasterize" one of them, we will get a correct solution.
To do so, we can represent the parallelepiped as two triangles and rasterize each of them individually. To rasterize a triangle, we need to select those cells which center is either inside of it, or located on the "top" or "left" edge of it. A "top" edge is an edge that is perfectly horizontal and whose defining vertices are above the third one. A "left" edge is an edge that is going up if we go in triangle's clockwise order.
This way, no cell is going to be selected twice in case we "rasterize" two triangles sharing an edge, and since we are tiling the plane with given parallelepipeds rasterized cells are exactly our solution.
If vectors ($$$dx_1$$$, $$$dy_1$$$) and ($$$dx_2$$$, $$$dy_2$$$) are either collinear or one of them is zero, the answer is "NO".
Also there is another solution. First of all we have to calculate $$$d$$$ — absolute value of determinant of the matrix formed by the given vectors:
$$$d = |det((dx_1, dy_1), (dx_2, dy_2))| = |dx_1 * dy_2 - dx_2 * dy_1|$$$
If given value $$$n$$$ is not equal to $$$d$$$ then there is no solution, in particular if $$$d=0$$$ there is no required $$$n$$$ pairs of integers.
Now let $$$n$$$=$$$d$$$ and $$$d_x$$$ = $$$gcd(dx_1, dx_2)$$$, $$$d_y$$$ = $$$gcd(dy_1, dy_2)$$$. Let's go to the same problem with smaller integers — we divide $$$dx_1$$$, $$$dx_2$$$ by $$$d_x$$$ and divide $$$dy_1$$$, $$$dy_2$$$ by $$$d_y$$$. Also we define $$$m=n/(d_x \cdot d_y)$$$ ($$$n$$$=$$$d$$$ so it is divisible by $$$d_x\cdot d_y$$$). So firstly we need to find such $$$m$$$ points $$$(x_i, y_i)$$$ that all values $$$(x_i + a \cdot dx_1 + b \cdot dx_2, y_i + a \cdot dy_1 + b \cdot dy_2)$$$ are different. It is enough for solution, because we still have $$$m$$$ equal to the absolute value of the determinant of the new matrix.
It turns out that it is easy to find such set of points. In particular we may choose points $$$(0,0), (0,1), \cdots, (0, m-1)$$$, i.e. $$$x_i=i$$$, $$$y_i=0$$$. Let's prove that such set is correct. Assume that for some non-zero pair $$$(a, b)$$$ and for some $$$j$$$ we also have one of these points: $$$x_i$$$ = $$$x_j + a \cdot dx_1 + b \cdot dx_2$$$ and $$$y_i$$$ = $$$y_j + a \cdot dy_1 + b \cdot dy_2$$$. Considering $$$y_i=y_j=0$$$, we have $$$a \cdot dy_1 + b \cdot dy_2 = 0$$$. Since $$$dy_1$$$ and $$$dy_2$$$ are coprime (we have divided it by $$$d_y$$$) $$$a = k \cdot dy_2$$$, $$$b = -k\cdot dy_1$$$ for some integer $$$k$$$. If we use this for $$$x$$$ equation, we will have: $$$x_i - x_j$$$ = $$$k \cdot dy_2 \cdot dx_1 - k \cdot dy_1 \cdot dx_2$$$. I.e. $$$x_i - x_j$$$ = $$$k \cdot (dx_1 \cdot dy_2 - dx_2 \cdot dy1)$$$ = $$$\pm k \cdot m$$$. Also $$$-m < x_i - x_j < m$$$ so this equation has no solution for integer non-zero $$$k$$$. Thus this set of points is correct.
Finally having such $$$m$$$ points we have to create an $$$n$$$-points solution for the original problem. Obviously we need to multiply current answer coordinates by $$$d_x$$$ and $$$d_y$$$. Then for each of these points, for each $$$0 \leq r_x < d_x$$$ and for each $$$0 \leq r_y < d_y$$$ we need to print a new point. So, the answer is $$$(i \cdot d_x + r_x, r_y)$$$ for each $$$0 \leq i < m$$$, $$$0 \leq r_x < d_x$$$, $$$0 \leq r_y < d_y$$$.