Wesley's Anger Contest 3 Problem 7 - Mirrors

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 3.0s
Memory limit: 512M

Authors:
Problem type

A set of N double sided mirrors are scattered on an integer coordinate plane uniformly at random. For simplicity, the i^{th} mirror can be thought of as a point at (x_i, y_i) 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 2-dimensional vector (v, w). This represents the laser travelling in a direction that makes an angle equal to \operatorname{arctan2}{(w, v)} relative to the x-axis.

Information on the \operatorname{arctan2} function can be found here in C++, here in Java, and here in Python.

The reflection behaviour of the i^{th} mirror can be described using 2 integers A_i and B_i. Suppose the current direction of the laser is (v, w). When the laser hits the i^{th} mirror, the direction of the laser changes to (A_i \cdot v + B_i \cdot w, B_i \cdot v - A_i \cdot w). It is guaranteed that this represents a rotation of 180 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 A_i and B_i 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 \lceil \frac{3N}{4} \rceil of the mirrors, and that the first \lceil \frac{3N}{4} \rceil of these mirrors are all distinct? The laser is considered to hit the mirror it starts from.

Note: \lceil x \rceil represents the smallest integer greater than or equal to x.

Constraints

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.

2 \le N \le 100\,000
1 \le x_i, y_i \le 10^6
|A_i|, |B_i| \le 2 \cdot 10^{12}

It is guaranteed that x_i and y_i are generated uniformly at random and that all mirror locations are distinct. Note that A_i and B_i are not necessarily generated uniformly at random.

Subtask 1 [10%]

2 \le N \le 4

Subtask 2 [10%]

2 \le N \le 400

Subtask 3 [20%]

2 \le N \le 10\,000

Subtask 4 [60%]

No additional constraints.

Input Specification

The first line contains a single integer N.

The next N lines describe the mirrors. Each line contains 4 integers, x_i, y_i, A_i, and B_i, indicating the i^{th} mirror is located at (x_i, y_i) and has a reflection behaviour described by the integers A_i and B_i.

Output Specification

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 \lceil \frac{3N}{4} \rceil of the mirrors, and that the first \lceil \frac{3N}{4} \rceil of these mirrors are all distinct, output -1 and only -1.

Otherwise, output \lceil \frac{3N}{4} \rceil distinct integers on a single line, the i^{th} of which is Z_i. This represents the laser being fired from mirror Z_1 in the direction of mirror Z_2, and will hit all mirrors from Z_1 to Z_{\lceil \frac{3N}{4} \rceil} in that order.

Mirrors are 1-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

-1

Sample Explanation 1

No matter which direction we fire the laser in, we can only hit at most 2 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 2 in the direction of mirror 3, the first 3 mirrors that are hit are 2, 3, and 4, in that order.


Comments

There are no comments at the moment.