С одного удара
С одного удара
Недавно Джанин отправилась в свой местный игровой магазин и купила "С одного удара" - новую игру в мини-гольф для своего компьютера. Как указано в названии, цель игры состоит в том, чтобы попасть шаром в отверстие, используя только один выстрел. В игре также заимствованы элементы из игр в стиле брейк-дробилок: в игровом поле расположено несколько стен, которые будут уничтожены после удара мяча. Количество удачных выстрелов зависит от количества разрушенных стен, поэтому Джанин задается вопросом: какое максимальное количество стен может быть поражено при выполнении "С одного удара"?
В этой задаче Вы можете представить игровое поле как декартову плоскость с исходным положением шара в начале координат. Стены являются непересекающимися осевыми параллельными отрезками в этой плоскости (то есть параллельно оси x или оси y). Диаметр шара пренебрежимо мал, поэтому он представляется как одна точка.
Всякий раз, когда мяч попадает в стену, происходят две вещи:
Направление шара изменяется обычным образом: угол падения равен углу отражения.
Стена, которую коснулся шар, уничтожена. Следуя общей логике видеоигр, не осталось ни одного обломка стены; то есть вся стена как бы исчезла.
Поведение шара также зависит от мощности выстрела. В частности, для оптимального выстрела может потребоваться сначала катить шар, затем ударить еще несколько стен, после чего только шар упадет в отверстие.
Входные данные
Состоит из:
строка с одним числом n (0 ≤ n ≤ 8) - количество стен;
строка с двумя целыми числами x и y - координатами лунки;
n строк с четырьмя целыми числами
x[1]
,y[1]
,x[2]
иy[2]
(либоx[1]
=x[2]
, либоy[1]
=y[2]
, но не одновременно) - описание стены с концами (x[1]
,y[1]
) и (x[2]
,y[2]
).
Лунка находится не в начале координат, и не на стене. Стены не касаются друг друга и не пересекаются. Никакая стена не находится полностью на оси x или оси y. Все координаты являются целыми числами и по модулю не превосходят 1000.
Выходные данные
Если невозможно выстрелить мяч так, чтобы он достиг лунки, выведите "impossible". Иначе выведите максимальное количество стенок, которые можно уничтожить используя один выстрел в игре "С одного удара".
Пример
3 4 2 1 1 1 2 2 1 2 2 3 1 3 2
2
1 2 0 1 -1 1 1
impossible
2 -2 4 2 4 2 2 0 6 -2 6
2