Планета Плюк
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
На планете Плюк, поверхность которой мы будем считать абсолютно плоской,
был разработан новый принцип перемещения единственного имеющегося там
транспортного средства — пепелаца. А именно, на расстоянии одного километра
друг от друга в точках `(0,\ 0)` и `(1,\ 0)` были построены две станции управления
пепелацами `A` и `B`. С помощью них можно мгновенно переместить любой пепелац,
повернув его на 90 градусов по или против часовой стрелки относительно
точки `A` или `B`. Расстояние от пепелаца до соответствующей станции при этом
не меняется. Следующее перемещение можно делать как относительно той
же станции, так и относительно другой.
Например, если повернуть пепелац, находящийся в точке `(3,\ 1)` на 90 градусов
против часовой стрелки относительно станции `A`, то он переместится в точку `(-1,\ 3)`,
если его затем повернуть на 90 градусов по часовой стрелке относительно станции
`B`, то он переместится в точку `(4,\ 2)`, если затем повернуть его вокруг
станции `B` по часовой стрелке еще раз, он переместиться в точку `(3,\ -3)`.
Один житель планеты недавно решил отправиться на своем пепелаце в гости к другу.
Житель проживает около точки с координатами `(x_1,\ y_1)`, а его друг —
около точки с координатами `(x_2,\ y_2)`. Помогите жителю с помощью станций
управления пепелацем оказаться как можно ближе к месту, где проживает
его друг, чтобы потом меньше было идти по пустыне.
Поскольку перемещения мгновенные и абсолютно бесплатные, то минимизировать количество
перемещений не надо.
Ввод
Входной файл содержит четыре целых числа — `x_1`, `y_1`, `x_2` и `y_2`,
они не превышают `10^4` по абсолютной величине.
Вывод
Выведите в выходной файл последовательность перемещений с использованием
станций управления, которая перемещает пепелац из точки `(x_1,\ y_1)`
как можно ближе к точке `(x_2,\ y_2)`.
Поворот по часовой стрелке
относительно станции `A` обозначается как "+A", поворот против
часовой стрелки относительно станции `A` обозначается как "-A",
соответствующие повороты относительно станции `B` обозначаются как
"+B" и "-B". Выводите по одному перемещению на строке.
Выведенная последовательность не обязана быть минимальной по количеству
перемещений, но должна содержать не более `10^6` действий.
Источник: VI Всероссийская командная олимпиада школьников по программированию, 2005