Задача 102937
|
Название задачи: Шагающий многоугольник . |
 |
Условие
На плоскости заданы выпуклый многоугольник 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 при каждом «шаге» отображать центрально-симметрично. Это ускоряет работу программы.
