Problem A. Gunman
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.
Constraints
2 ≤ n ≤ 100; 0 < x
1i, y
1i, x
2i, y
2i, z
i < 1000
Sample tests
| No. |
Input file (gunman.in) |
Output file (gunman.out) |
|---|
| 1 |
3
1 3 5 5 3
1 2 5 7 5
5 2 7 6 6
|
SOLUTION
-1.000000
2.000000 3.000000 3.000000
4.000000 5.000000 5.000000
5.000000 6.000000 6.000000
|
| 2 |
3
2 1 5 4 1
3 5 6 8 2
4 3 8 6 4
|
UNSOLVABLE
|
Задача B. Сухой фотограф
Условие
В некотором городе имеется достопримечательность - прямоугольная площадь размером X на Y метров, на которой работают N фонтанов. Турист желает посетить эту площадь и сделать несколько фотографий. Однако если при фотографировании находиться от какого-либо из фонтанов на расстоянии меньше R метров, фотоаппарат может быть поврежден брызгами воды. Помогите фотографу найти безопасную точку съёмки.
Требуется по координатам фонтанов определить точку на площади, удалённую от каждого из них не менее чем на R метров, или определить, что такой точки не существует. Если таких точек более одной, вывести любую из них.
Обратите внимание, что стоять в точности на границе окружности или прямоугольника разрешено.
Формат входного файла
В первой строке входного файла содержатся числа X Y N R, в каждой из следующих N строк - координаты x
i y
i i-го фонтана. Числа X Y R во входном файле — вещественные.
Формат выходного файла
В выходном файле должны, содержаться два вещественных числа - координаты сухой точки. Если такой точки не существует, следует вывести значения -1 -1.
Проверка результатов будет осуществляться путём подстановки координат точки в неравенства, задающие внутренность каждого круга. Эти вычисления будут производиться с использованием вещественных чисел двойной точности (double).
Ограничения
1 <= N <= 100, 1 <= X, Y, R <= 10
6.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
100 100 4 50
0 0
100 0
0 100
100 100
|
50 50
|
