A set of double sided mirrors are scattered on an integer coordinate plane uniformly at random. For simplicity, the mirror can be thought of as a point at with an infinitesimally small radius. You will fire a laser starting at one of the mirrors in the direction of a different mirror. When a laser hits a mirror, it will reflect off the mirror and continue in its new direction until it hits another mirror (or forever if it never hits another mirror).
We can describe the direction the laser is travelling in using a -dimensional vector . This represents the laser travelling in a direction that makes an angle equal to relative to the -axis.
The reflection behaviour of the mirror can be described using integers and . Suppose the current direction of the laser is . When the laser hits the mirror, the direction of the laser changes to . It is guaranteed that this represents a rotation of degrees, followed by a reflection across a line passing through the origin, and finally a scalar multiplication of the resulting vector.
Side Note: There is nothing special about this reflection behaviour; it works the same way as a conventional mirror. The purpose of providing and is to avoid floating point precision errors.
Can you determine if you can fire a laser starting at one of the mirrors in the direction of a different mirror, such that it hits at least of the mirrors, and that the first of these mirrors are all distinct? The laser is considered to hit the mirror it starts from.
Note: represents the smallest integer greater than or equal to .
For this problem, you will NOT be required to pass ANY of the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.
It is guaranteed that and are generated uniformly at random and that all mirror locations are distinct. Note that and are not necessarily generated uniformly at random.
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [20%]
Subtask 4 [60%]
No additional constraints.
The first line contains a single integer .
The next lines describe the mirrors. Each line contains integers, , , , and , indicating the mirror is located at and has a reflection behaviour described by the integers and .
If you cannot fire a laser starting at one of the mirrors in the direction of a different mirror, such that it hits at least of the mirrors, and that the first of these mirrors are all distinct, output
-1 and only
Otherwise, output distinct integers on a single line, the of which is . This represents the laser being fired from mirror in the direction of mirror , and will hit all mirrors from to in that order.
Mirrors are -indexed and based on the order of the input.
Note that for this problem, a verdict involving Presentation Error indicates that your output format is incorrect, (including, but not limited to not outputting the correct number of distinct integers.
Sample Input 1
4 1 1 -1 0 1 3 -1 0 3 3 -1 0 3 1 -1 0
Sample Output 1
Sample Explanation 1
No matter which direction we fire the laser in, we can only hit at most mirrors. The mirrors are represented as coloured line segments in the image, however they do not actually take up more than a single point in space.
Sample Input 2
4 1 1 0 -1 1 3 0 1 3 3 0 -1 3 1 0 1
Sample Output 2
2 3 4
Sample Explanation 2
If we fire the laser starting from mirror in the direction of mirror , the first mirrors that are hit are , , and , in that order.