We are in the process of building a mechanical system to rule the world. All that is left is to find a way to rotate a rod at a specific rate. There is an engine in the system that rotates its own shaft at a fixed unit angular velocity. Help us place our gears properly to transmit the rotational motion to the required rod. Rods can only be placed in our system in vertical position at the grid points of a horizontal NxM grid. Right now there are only two rods: the rotated shaft is at the (X0,Y0) position and the rod we want to rotate is at the (X1,Y1) position. | ![]() |
At most two gears can be placed on each rod: one at a lower level and another at a higher level. Gears rotate together with the rods they are attached to.
Transmission of rotation works the following way: Given two rods at distance D12 (one of which is already rotating), placing a gear with radius R1 on one and a gear with radius R2 on the other, the rotation is transmitted if R1 + R2 = D12 and the two gears are on the same level. The rotation speed V1 and V2 of the two rods (and of the two gears) will be such that R1*V1 = -R2*V2. (Note that the rotation speed has a sign and that two meshing gears rotate in different directions).
Gears on the same level must not intersect with each other, so R1 + R2 <= D12 must hold. Gears must not intersect with an already placed rod either, so R1 < D12 must hold as well (in case there is no gear on the other rod on the same level). A single rod cannot be rotated from more than one sources at the same time (so a gear must not mesh with two or more other already rotating gears).
The first line of the input contains three integers: N, M and L. N, M is the size of the grid and L is the number of gear types we have.
The second line contains X0, Y0, X1, Y1 and V. (X0,Y0) are the coordinates of the rod rotating at unit speed, (X1,Y1) are the coordinates of the rod we want to rotate at speed V. V is a signed rational number given in the fractional form A/B where A and B are integers.
The following L lines list the gears we have: Each line contains two integers R and C, meaning that we have C number of gears with radius R.
The first line of the output should contain K, the number of used gears.
The next K lines each describes a gear in the system with four integers: X, Y, R and H. (X,Y) are the coordinates of the rod the gear is attached to (must be in the (0,0), (N-1,M-1) rectangle), R is the radius and H is the level it is placed at, which is either 0 or 1.
Rods are assumed to be placed at positions where a gear is placed.
The required rotation speed must be exactly met.
You don't need to use all the gears we have.
5 7 4 0 0 6 1 -3/2 1 3 2 2 3 2 4 1
5 0 0 3 0 3 4 2 0 3 4 1 1 6 4 2 1 6 1 1 1
Each solved input is worth 100 points.