Задача №418. Планета Плюк
На планете Плюк, поверхность которой мы будем считать абсолютно плоской, был разработан новый принцип перемещения единственного имеющегося там транспортного средства – пепелаца. А именно, на расстоянии одного километра друг от друга в точках (0, 0) и (1, 0) были построены две станции управления пепелацами A и B. С помощью них можно мгновенно переместить любой пепелац, повернув его на 90 градусов по или против часовой стрелки относительно точки A или B. Расстояние от пепелаца до соответствующей станции при этом не меняется. Следующее перемещение можно делать как относительно той же станции, так и относительно другой.
Например, если повернуть пепелац, находящийся в точке (3, 1) на 90 градусов против часовой стрелки относительно станции A, то он переместится в точку (- 1, 3), если его затем повернуть на 90 градусов по часовой стрелке относительно станции B, то он переместится в точку (4, 2), если затем повернуть его вокруг станции B по часовой стрелке еще раз, он переместиться в точку (3, - 3).
Один житель планеты недавно решил отправиться на своем пепелаце в гости к другу. Житель проживает около точки с координатами (x1, y1), а его друг – около точки с координатами (x2, y2). Помогите жителю с помощью станций управления пепелацем оказаться как можно ближе к месту, где проживает его друг, чтобы потом меньше было идти по пустыне.
Поскольку перемещения мгновенные и абсолютно бесплатные, то минимизировать количество перемещений не надо.
На вход программы поступают четыре целых числа – x1, y1, x2 и y2, они не превышают 104 по абсолютной величине.
Выведите последовательность перемещений с использованием станций управления, которая перемещает пепелац из точки (x1, y1) как можно ближе к точке (x2, y2).
Поворот по часовой стрелке относительно станции A обозначается как «+A», поворот против часовой стрелки относительно станции A обозначается как «-A», соответствующие повороты относительно станции B обозначаются как «+B» и «-B». Выводите по одному перемещению на строке.
Выведенная последовательность не обязана быть минимальной по количеству перемещений, но должна содержать не более 106 действий.
3 1 3 -3
+A -B -B +A +A -B -B +A
0 0 3 0
-A +B +A -B