Шагающий многоугольник
На плоскости заданы выпуклый многоугольник M и точка P(x, y). За один ход
разрешается центрально-симметрично отразить многоугольник относительно
середины любой из его сторон. Требуется найти последовательность ходов, в
результате которой точка P оказалась бы накрытой этим многоугольником.
Входные данные
Во входном файле записано количество вершин многоугольника N (3 ≤
N ≤ 20) и координаты точки x и y. Далее перечислены координаты вершин
многоугольника в порядке обхода по часовой стрелке. Все координаты – целые
числа, не превосходящие по абсолютной величине 105.
Выходные данные
Если точку P накрыть нельзя, запишите в выходной файл сообщение
«Impossible». В противном случае выведите в него последовательность
ходов, после выполнения которой многоугольник M накроет точку P. Каждый
ход задается номерами вершин той стороны, относительно середины которой
производится преобразование центральной симметрии. Вершины
многоугольника нумеруются начиная с 1.
Пример входного файла
3 3 2
0 1 1 2 1 0
Пример выходного файла
2 3
3 1
2 3
Решение
Выполнение двух «шагов» многоугольника M относительно середин двух
различных его сторон приводит к параллельному переносу M на удвоенный
вектор, соединяющий середины этих сторон. Взяв, например, первые три
стороны многоугольника M, мы получим два неколлинеарных вектора сдвига.
Параллельными переносами M вдоль этих векторов можно достаточно близко
приблизить его к точке P. Далее нужно устроить перебор, то есть
последовательно проделывать «шаги» относительно одной, двух и т.д. сторон M
и проверять, принадлежит ли точка полученному многоугольнику или нет.
Можно доказать, что точку всегда можно накрыть, поэтому и описанный
алгоритм ответ находит всегда.
Заметим, что можно считать многоугольник M неподвижным, а точку P при
каждом «шаге» отображать центрально-симметрично. Это ускоряет работу
программы.