Хексзмеи в хексболоте
Хексболото - это странный тип болота, вымощенного правильными шестиугольными ямочками. Хексзмеи ползают в нем, являясь адаптированными к окружающей среде. Они представляют собой цепочку правильных шестиугольников, каждый из которых строго полностью помещается в одну шестиугольную ямочку.
Хексзмеи передвигают свои секции с ямок в которых они находятся, на соседние. Чтобы не сломать свое тело, части хексзмей, которые были соседними до совершения движения, остаются соседними и после. Когда двигается одна из секций, то прилегающие к ней секции способствуют движению и поэтому не могут двигаться в одно и то же время. Любое число секций, никакие две из которых не являются соседними, могут передвигаться одновременно.
Можно заметить, что хексзмея может передвигать свои секции, находящиеся на концах, в одну из двух ямок, а промежуточные секции только в одну, если такая существует.
Например, в случае отсутствия препятствий, хексзмеи могут ползти вперед, извивая свое тело, как показано на Рисунке 1, слева направо. На рисунке змея в каждый момент времени передвигает четыре свои части тела из восьми, и передвигает все свое тело вперед на длину одной ямки после четырех шагов движения. На самом деле, они намного лучше ползают боком, как вьющиеся растения.
Рисунок1: Ползание вперед
Их кожа настолько липкая, что если две секции которые изначально не были соседними, попадут в соседние ямки (Рисунок 2), то они склеятся вместе и змея умрет. Две секции не могут уместиться в одной ямке. Это конечно же сковывает передвижение змеи. Иногда им приходится приложить некоторые усилия, чтобы достать кусок еды, даже если он находится в ямке рядом с головой.
Рисунок 2: Смертельный случай
И там и тут на хексболоте находятся скалы. Каждая скала умещается в точности в одну ямку. Кожа хексзмей не прилипает к скалам, однако змеи не могут заползать на них. И хотя ямки со скалами ограничивают передвижение змей, они в свою очередь хорошо знают географию местности и могут планировать свое передвижение по кратчайшему маршруту.
Вас назначили руководителем группы ученых, которая занимается проведением научных исследований змей на этом болоте. Вам следует завершить начатое исследование, но не в ущерб любой аварии. Ваша задача - оценить как скоро хексзмея, питающаяся людьми, переместит свою голову (первую секцию) в позицию болота, где находится ученый. Секции тела змеи кроме головы безвредны, и ученый, одетый в хай-тек антиприлипающий костюм, может находиться с любой из секцией тела в одной ямке.
Входные данные
Входные данные состоят из нескольких тестов, последняя строка содержит один ноль. Количество тестов не превосходит 10.
Каждый тест имеет следующий формат.
количество секций у змеи (=n)
x1 y1
x2 y2
...
xn yn
количество скал на болоте (=k)
u1 v1
u2 v2
...
uk vk
X Y
Первая строка каждого теста содержит число n - количество секций у змеи, оно равно 2 или более, но никогда не превосходит 8. Каждая из следующих n строк содержит x и y координаты секции змеи. Строки описывают начальное положение секций в порядке от головы до хвоста.
Следующая строка задает количество скал k в болоте, это число не отрицательное и не превышает 100. Каждая из следующих k строк содержит два целых числа u и v - положение скалы.
Последняя строка содержит два целых числа X и Y - позиция, куда необходимо приползти змее. Голова змеи изначально не находится здесь.
Все значения координат x, y, u, v, X и Y лежат в интервале от -999999 до 999999 включительно. Два числа в строке разделены одним пробелом. Во входных данных не встречаются другие символы, кроме как десятичные цифры, знак минус и пробелы, их разделяющие. Система координат, кодирующая позиции, показана на Рисунке 3.
Рисунок 3: Система координат
Выходные данные
Для каждого теста вывести строку, содержащую целое число - наименьшее количество шагов, необходимое змее передвинуть свою голову в заданную позицию. Выходные строки не должны содержать никаких других символов.
Считайте, что хексзмеи могут найти решение не более чем за 20 шагов.