eolymp
bolt
Try our new interface for solving problems
Məsələlər

Снайперский выстрел

Снайперский выстрел

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 16 MiB

В точке S висит снайпер. Его задача — ликвидировать врага государства, который едет на велосипеде по прямой из точки A в точку B. Пуля, выпущенная снайпером, летит по прямой с бесконечной скоростью. В городе построены n небоскрёбов, представляющих собой прямоугольные параллелепипеды. Пуля не может пробивать небоскрёб насквозь, но может касаться его поверхности. Естественно, снайпер произведёт успешный выстрел как можно раньше.

Вы должны посчитать координаты точки, в которой будет находиться враг государства в момент выстрела.

Giriş verilənləri

В первой строке через пробел записаны координаты точки S: s_x, s_y, s_z (s_z0). Во второй строке через пробел записаны координаты точек A и B: a_x, a_y, b_x, b_y. Враг государства перемещается по поверхности земли, поэтому его z-координата всегда равна нулю. В третьей строке записано целое число n (0n100). В каждой из следующих n строк через пробел записаны числа l_x, l_y, r_x, r_y, h (l_x < r_x; l_y < r_y; h > 0) — координаты противоположных углов основания очередного небоскрёба и его высота. Стороны небоскрёбов параллельны осям координат. Все координаты и высоты целые и не превосходят по модулю 100. Гарантируется, что никакие два небоскрёба не имеют общих точек, точка S не лежит внутри или на границе небоскрёба, отрезок AB не имеет общих точек ни с каким небоскрёбом.

Çıxış verilənləri

Если врага государства ликвидировать не получится, выведите "Impossible". Иначе выведите координаты точки, в которой будет находится враг государства в момент выстрела, с точностью не менее 10^{−7}.

Nümunə

Giriş verilənləri #1
0 0 2
-4 4 4 4
2
-3 2 -1 3 10
1 -1 4 2 20
Çıxış verilənləri #1
-1.3333333333 4.0000000000
Müəllif Алексей Самсонов
Mənbə Ural SU Contest. Petrozavodsk Winter Session, February 2009