Задача 2: Лазерная пушка
У игрока в космической стрелялке есть очень мощная лазерная пушка. Но она неподвижна и может стрелять только в одном направлении. Игрок может расставить на игровом поле двусторонние зеркала, меняющие ход луча, чтобы поражать врагов.
Введём декартову систему координат с центром, где расположена пушка, то есть пушка имеет координаты (0; 0). Пушка стреляет в направлении точки (1; 1). Игрок может поставить зеркала в точках с целочисленными координатами. Зеркала могут быть горизонтальными или вертикальными, попадание луча в зеркало меняет траекторию луча по законам отражения света. Некоторые возможные варианты отражения луча от зеркала изображены на рисунке.
(РИСУНОК 1)
Вам необходимо расставить минимальное количество зеркал так, чтобы лазерный луч поразил цель.
Входные данные
Программа получает на вход два целых числа X и Y, не превосходящих по модулю 10000, записанные в разных строках — координаты цели. Точка (X; Y) не совпадает с началом координат.
Выходные данные
Программа должна вывести в первой строке число N — необходимое количество зеркал.
Следующие N строк должны содержать информацию о каждом зеркале. В i-й строке должны быть записаны через пробелы два целых числа xi и yi и один символ ti, обозначающие координаты (xi; yi) точки, в которых установлено i-е зеркало, и тип этого зеркала ti. Если ti является символом «V», то i-е зеркало размещено вертикально, если же ti является символом «H», то зеркало размещено горизонтально. Например, строка «-2 5 H» обозначает горизонтальное зеркало в точке (-2; 5). Зеркала можно выводить в любом порядке. Зеркало нельзя размещать в точке (0; 0), также нельзя размещать два зеркала в одной точке. Значения xi и уi не должны по модулю превосходить 100000. Также, разумеется, нельзя допустить, чтобы отражённый луч попал в пушку.
Если вариантов ответа несколько, выведите любой из них.
Если поразить цель в соответствии с условиями задачи невозможно, программа должна вывести одно число «-1».
Если для поражения цели зеркала не нужны, программа должна вывести одно число «0».
Система оценивания
Решения, правильно работающие только для X ≥ 0 и Y ≥ 0, будут оцениваться в 35 баллов.
Пример
У игрока в космической стрелялке есть очень мощная лазерная пушка. Но она неподвижна и может стрелять только в одном направлении. Игрок может расставить на игровом поле двусторонние зеркала, меняющие ход луча, чтобы поражать врагов.
Введём декартову систему координат с центром, где расположена пушка, то есть пушка имеет координаты (0; 0). Пушка стреляет в направлении точки (1; 1). Игрок может поставить зеркала в точках с целочисленными координатами. Зеркала могут быть горизонтальными или вертикальными, попадание луча в зеркало меняет траекторию луча по законам отражения света. Некоторые возможные варианты отражения луча от зеркала изображены на рисунке.
(РИСУНОК 1)
Вам необходимо расставить минимальное количество зеркал так, чтобы лазерный луч поразил цель.
Входные данные
Программа получает на вход два целых числа X и Y, не превосходящих по модулю 10000, записанные в разных строках — координаты цели. Точка (X; Y) не совпадает с началом координат.
Выходные данные
Программа должна вывести в первой строке число N — необходимое количество зеркал.
Следующие N строк должны содержать информацию о каждом зеркале. В i-й строке должны быть записаны через пробелы два целых числа xi и yi и один символ ti, обозначающие координаты (xi; yi) точки, в которых установлено i-е зеркало, и тип этого зеркала ti. Если ti является символом «V», то i-е зеркало размещено вертикально, если же ti является символом «H», то зеркало размещено горизонтально. Например, строка «-2 5 H» обозначает горизонтальное зеркало в точке (-2; 5). Зеркала можно выводить в любом порядке. Зеркало нельзя размещать в точке (0; 0), также нельзя размещать два зеркала в одной точке. Значения xi и уi не должны по модулю превосходить 100000. Также, разумеется, нельзя допустить, чтобы отражённый луч попал в пушку.
Если вариантов ответа несколько, выведите любой из них.
Если поразить цель в соответствии с условиями задачи невозможно, программа должна вывести одно число «-1».
Если для поражения цели зеркала не нужны, программа должна вывести одно число «0».
Система оценивания
Решения, правильно работающие только для X ≥ 0 и Y ≥ 0, будут оцениваться в 35 баллов.
Пример
| Ввод | Вывод | Пояснение |
|---|---|---|
| 5 1 | 1 3 3 H | Ниже приведён рисунок, соответствующий этому примеру. (рис 2) |