eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

С одного удара

С одного удара

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Недавно Джанин отправилась в свой местный игровой магазин и купила "С одного удара" - новую игру в мини-гольф для своего компьютера. Как указано в названии, цель игры состоит в том, чтобы попасть шаром в отверстие, используя только один выстрел. В игре также заимствованы элементы из игр в стиле брейк-дробилок: в игровом поле расположено несколько стен, которые будут уничтожены после удара мяча. Количество удачных выстрелов зависит от количества разрушенных стен, поэтому Джанин задается вопросом: какое максимальное количество стен может быть поражено при выполнении "С одного удара"?

В этой задаче Вы можете представить игровое поле как декартову плоскость с исходным положением шара в начале координат. Стены являются непересекающимися осевыми параллельными отрезками в этой плоскости (то есть параллельно оси x или оси y). Диаметр шара пренебрежимо мал, поэтому он представляется как одна точка.

prb7869.gif

Всякий раз, когда мяч попадает в стену, происходят две вещи:

  • Направление шара изменяется обычным образом: угол падения равен углу отражения.

  • Стена, которую коснулся шар, уничтожена. Следуя общей логике видеоигр, не осталось ни одного обломка стены; то есть вся стена как бы исчезла.

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

Входные данные

Состоит из:

  • строка с одним числом n (0n8) - количество стен;

  • строка с двумя целыми числами 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". Иначе выведите максимальное количество стенок, которые можно уничтожить используя один выстрел в игре "С одного удара".

Пример

Входные данные #1
3
4 2
1 1 1 2
2 1 2 2
3 1 3 2
Выходные данные #1
2
Входные данные #2
1
2 0
1 -1 1 1
Выходные данные #2
impossible
Входные данные #3
2
-2 4
2 4 2 2
0 6 -2 6
Выходные данные #3
2
Источник 2015 ACM North Western European Regional Contest (NWERC), Ноябрь 30, Задача H