Georgiy Korneev (original idea), Roman Elizarov (text)
Time limit:
2 sec
Input file:
gunman.in
Memory limit:
64 Mb
Output file:
gunman.out
Statement
Consider a 3D scene with OXYZ coordinate system. Axis
OX points to the right, axis OY points up, and
axis OZ points away from you. There is a number
of rectangular windows on the scene. The plane of each window
is parallel to OXY, its sides are parallel to OX and OY.
All windows are situated at different depths
on the scene (different coordinates z > 0).
A gunman with a rifle moves along OX axis (y = 0 and z = 0).
He can shoot a bullet in a straight line. His goal is to
shoot a single bullet through all the windows. Just touching a window
edge is enough.
Your task is to determine how to make such shot.
Input file format
The first line of the input file contains a single integer number n
— the number of windows on the scene. The following
n lines describe the windows. Each line contains five integer numbers
x1i, y1i, x2i, y2i, zi.
Here (x1i, y1i, zi) are coordinates of the bottom left corner of the
window, and (x2i, y2i, zi) are coordinates of the top right corner
of the window (x1i < x2i, y1i < y2i).
Windows are ordered by z coordinate (zi > zi-1
for 2 ≤ i ≤ n).
Output file format
Output a single word 'UNSOLVABLE' if the gunman cannot
reach the goal of shooting a bullet through all the windows.
Otherwise, on the first line output a word 'SOLUTION'.
On the next line output x coordinate of the point from which
the gunman must fire a bullet. On the following n lines output x, y, z
coordinates of the points where the bullet goes through the consecutive
windows. All coordinates in the output file must be printed with
six digits after decimal point.
