A guided probe is launched from the space station located at the distance of h from the surface of a large asteroid. The probe must land at the asteroid. The probe moves straight forward for a fixed distance d, after that it receives a new command from the station. The command defines the new direction for the movement. Each movement of the probe must help it to get closer to the surface. The control signals from the station are transmitted only within a cone having a vertex angle of α.
So, the trajectory of the probe is a broken line with segments of equal length, which is lying inside the cone described above. The last segment of the trajectory must also be of length d, lie inside the transmission cone and end at the surface of the asteroid.
Your task is to determine if it is possible to perform the landing of the probe taking into consideration the above conditions. If the landing is possible, then find the trajectory of minimal length including the coordinates of the ends of each segment. The landing point must be found, too.
The coordinates of the points are Cartesian. Ox and Oy lie on the surface of the asteroid, and Oz passes through the space station.
h (0 < h < 100), d (h/1000 ≤ d ≤ 10*h), α (the angle is in radians, 0.1 ≤ α ≤ 3). All numbers are float.
n — the number of segments in the trajectory, or −1, if landing is impossible
x1 y1 z1
x2 y2 z2
xn yn zn — the coordinates of the points where the probe receives control signals, and the landing point. All coordinates must be calculated to within 0.0001.
11 5 2
0 3 7
3 3 3
3 –1 0
Problem Source: 2002-2003 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 2002