Шестиугольные палочки
Рассмотрим бесконечную шестиугольную сетку. Сетка состоит из одинаковых правильных шестиугольных ячеек, расположенных как указано ниже. На рисунке также представлена система координат, используемая для идентификации каждой ячейки. Каждая ячейка сетки может быть либо пустой, либо заблокированной.
Рисунок: Часть сетки
Несколько палочек положили произвольным образом на сетку. Длина каждой палочки равна одной 'шестиугольной единице'. Это значит, что концы палочки расположены в центрах соседних ячеек. Вам следует передвинуть палочки таким образом, чтобы получить замкнутый правильный шестиугольник.
На рисунках ниже приведены примеры замкнутых шестиугольников, сделанных из палочек.
Вам заданы начальные координаты палочек, размещенных на сетке. Также будут заданы координаты заблокированных ячеек. За каждый ход можно совершить одну из следующих операций:
Выберите одну палочку и выкиньте ее
Выберите одну палочку и поверните ее на 60 градусов по/против часовой стрелки вокруг одного из ее концов
Выберите одну палочку и протолкните ее на длину палочки.
Палочки никогда не должны занимать заблокированные ячейки. Однако две палочки могут занимать одну и ту же ячейку одновременно.
Рассмотрим состояние сетки выше. Препятствие находится в ячейке с координатами (1, 1), а концы палочек в ячейках (0, 0) - (1, 0). Четыре возможные операции над палочкой представлены ниже
По завершению всех операций на сетке должен образоваться замкнутый правильный шестиугольник без вокруг лежащих палочек. Это значит, что на сетке находится в точности 6*x палочек, где x - натуральное число. Можете ли Вы совершить это за наименьшее количество операций?
Входные данные
Первая строка содержит количество тестов T (T < 50). Каждый тест начинается с количества имеющихся палочек S (S < 9). Следующие S строк описывают координаты палочек в формате x_1 y_1 x_2 y_2, что означает палочку от (x_1, y_1) до (x_2, y_2). Координаты корректны, а длина каждой палочки равна шестиугольной единице, как указано выше. В следующей строке задается количество препятствий B ( B < 20). Каждая из следующих B строк задает координаты препятствия. Координаты имеют формат x_1 y_1. Гарантируется, что препятствия не пересекаются ни с какой из палочек. Все координаты (палочек и препятствий) лежат в промежутке [-4, 4].
Замечание: Помните, что мы имеем дело с бесконечной сеткой. Поэтому в ответе координаты палочек могут лежать вне промежутка [-4, 4].
Выходные данные
Для каждого теста вывести его номер, за которым следует наименьшее количество требуемых операций. Если сформировать шестиугольник из палочек невозможно, то вывести "impossible". Придерживайтесь приведенного формата входных и выходных данных.