Laser Deflection Simulation

SHTSC has invented a new device called the Laser Generator capable of producing high‐energy lasers. Viewed from above, the generator appears as an infinite plane containing a directional laser emitter and several laser deflection devices (represented as line segments). When the emitter shoots out a ray, it may encounter these deflection devices. When a ray hits one of them, if it is not parallel to the device, the ray will be deflected. Unlike ordinary mirrors, each deflection device has a fixed deflection coefficient \(\lambda\) and the relationship between the incident angle \(\alpha\) and the exit angle \(\beta\) is given by:

[ \beta = \lambda \alpha ]

Notes:

• The incident angle is defined as the angle between the incoming ray and the normal of the device's surface.
• Both sides of a deflection device can deflect the laser.
• If the laser hits the device parallel to it (i.e. \(\alpha = \frac{\pi}{2}\)), no deflection occurs.
• If the ray (not parallel) hits an endpoint of a device, it is considered as a deflection.
• If \(\beta > \frac{\pi}{2}\) the laser may be deflected to the other side.

Your task is to simulate the operation of this laser generator. Given the emitter position and its initial direction, along with a set of deflection devices (each defined by the endpoints of its line segment and its deflection coefficient \(\lambda\)), determine which devices actually deflect the laser (in the order in which deflections occur).

Simulation Details:

The laser emitter is given by its coordinate \(P=(x,y)\) and initial shooting angle \(\theta\) (in degrees, measured counterclockwise from the positive x-axis). Each deflection device is a line segment defined by its endpoints \(A=(x_1,y_1)\) and \(B=(x_2,y_2)\) with a deflection coefficient \(\lambda\). The laser travels as a ray (half-line). When the ray intersects a deflection device, consider the following:

1. Compute the intersection point. If multiple devices are hit, use the one with the smallest positive distance from the current laser position.
2. For the current device, let \(\vec{T}\) be the unit tangent vector along the device. There are two possible unit normal vectors; choose the one \(\vec{n}\) for which \(\vec{v} \cdot \vec{n} > 0\) (where \(\vec{v}\) is the incident ray direction).
3. Let \(\alpha\) be the angle between \(\vec{v}\) and \(\vec{n}\). If \(\alpha\) is (nearly) \(\frac{\pi}{2}\) (i.e. the ray is parallel to the device), then no deflection occurs and the ray continues in the same direction.
4. If deflection occurs, compute \(\beta = \lambda \alpha\). Then:
   • If \(\beta \leq \frac{\pi}{2}\), the new ray direction \(\vec{v'}\) is given by \[ \vec{v'} = \cos\beta\, \vec{n} + \sin\beta\, \vec{t}, \] where \(\vec{t}\) is the unit tangent vector chosen to have the same sign as the projection of \(\vec{v}\) on the tangent direction.
   • If \(\beta > \frac{\pi}{2}\), let \(\delta = \pi - \beta\) (which is less than \(\frac{\pi}{2}\)), and then \[ \vec{v'} = \cos\delta\, (-\vec{n}) + \sin\delta\, \vec{t}. \]
5. Update the current position to the intersection point (shifted by a tiny epsilon along \(\vec{v'}\) to avoid precision issues) and continue the simulation with \(\vec{v'}\) as the new ray direction.
6. The simulation stops if no further intersection occurs or if a safe iteration limit is reached.

Output the 1-indexed indices of all deflection devices that actually deflected the laser, in order of occurrence. If the laser is never deflected, output 0.

inputFormat

The input consists of the following:

1. One line with three numbers: x y θ, where x and y are the coordinates of the laser emitter and θ is the initial shooting angle in degrees.
2. One line with an integer n indicating the number of deflection devices.
3. Then n lines follow, each containing five numbers: x1 y1 x2 y2 λ, where (x1,y1) and (x2,y2) are the endpoints of a deflection device and λ is its deflection coefficient.

outputFormat

Output a single line. If the laser is deflected by one or more devices, output their 1-indexed indices in the order they deflect the laser, separated by spaces. If the laser is never deflected, output 0.

sample

0 0 45
1
1 0 1 1 1

1