В точке S висит снайпер. Его задача — ликвидировать врага государства, который едет на велосипеде по прямой из точки A в точку B. Пуля, выпущенная снайпером, летит по прямой с бесконечной скоростью. В городе построены n небоскрёбов, представляющих собой прямоугольные параллелепипеды. Пуля не может
пробивать небоскрёб насквозь, но может касаться его поверхности. Естественно, снайпер произведёт успешный выстрел как можно раньше. Вы должны посчитать координаты точки, в которой будет находиться враг государства в момент выстрела.
Исходные данные
В первой строке через пробел записаны координаты точки S: sx, sy, sz (sz ≥ 0). Во второй строке через пробел записаны координаты точек A и B: ax, ay, bx, by. Враг государства перемещается по поверхности земли, поэтому его z-координата всегда равна нулю. В третьей строке записано целое число n (0 ≤ n ≤ 100). В каждой из следующих n строк через пробел записаны числа lx, ly, rx, ry, h (lx < rx; ly < ry; h > 0) — координаты противоположных углов основания очередного небоскрёба и его высота. Стороны небоскрёбов параллельны осям координат. Все координаты и высоты целые и не превосходят по модулю 100. Гарантируется, что никакие два небоскрёба не имеют общих точек, точка S не лежит внутри или на границе небоскрёба, отрезок AB не имеет общих точек ни с каким небоскрёбом.
Результат
Если врага государства ликвидировать не получится, выведите «Impossible». Иначе выведите координаты точки, в которой будет находится враг государства в момент выстрела, с точностью не менее 10−7.
Примеры
исходные данные | результат |
---|
0 0 2
-4 4 4 4
2
-3 2 -1 3 10
1 -1 4 2 20
| -1.3333333333 4.0000000000
|
0 0 2
4 1 4 -1
1
1 -1 3 1 10
| Impossible
|
Автор задачи: Алексей Самсонов
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, February 2009