
PINBOLL	Пинболл PINBALL Описание Поле в Pinball представляет собой прямоугольник без стенок, состоящий из n×m квадратных клеток (n клеток по вертикали, m клеток по горизонтали). Клетки по вертикали нумеруются сверху вниз, по горизонтали - слева направо. В каждой клетке можно установить одну отражающую пластинку в одном из двух положений: в положении 1 - от левого верхнего угла к правому нижнему или в положении 2 - от левого нижнего к правому верхнему. Летящий шарик при столкновении с пластинкой изменяет свою траекторию, при этом угол падения шарика всегда равен углу отражения и составляет 45° (см. рисунок) На границе прямоугольника заданы две точки А и В, являющиеся серединами сторон некоторых клеток поля. Пластинки расставляются таким образом, чтобы шарик, запущенный из точки А, попал в точку В. При этом шарик начинает движение внутрь поля перпендикулярно стороне клетки, на которой находится точка А Изначально на поле были расставлены k пластинок таким образом, чтобы шарик попал из точки А в точку В. После этого одну из пластинок удалили. Необходимо определить, куда и как можно поставить удаленную пластинку, чтобы шарик, выпущенный из точки А, попал в точку В. При этом требуется, чтобы длина пути шарика была минимальной. Пластинку нужно поставить на некоторую свободную клетку даже в том случае, если шарик попадает в точку В и без нее. Задача Требуется написать программу PINBALL (ограничение по памяти 64 мегабайта), устанавливающую пластинку таким образом, чтобы шарик попадал из точки А в точку В и длина его пути была минимальна. Формат входных данных Первая строка входного файла PINBALL.IN содержит три числа: n,m (1<=n,m<=1000) и k, где k - общее количество пластинок, которые были исходно расставлены. Во второй строке указываются номера клетки по вертикали и по горизонтали, на границе которой лежит точка А, и номер стороны, на которой она находится. Стороны клетки пронумерованы целыми числами от 1 до 4, при этом верхней стороне присвоен номер 1, далее по часовой стрелке нумеруются остальные стороны. Третья строка содержит описание точки В в том же формате. Следующие k-1 строк описывают пластинки, оставшиеся на поле. В каждой строке записаны по три числа: первое - номер клетки по вертикали, второе - номер клетки по горизонтали, третье - положение пластинки в клетке (число 1 или 2). Формат выходных данных Выходной файл PINBALL.OUT должен содержать три числа: номера клетки, в которую следует поставить пластинку, по вертикали и горизонтали и ее положение. Если решений несколько, выведите любое. Например: PINBALL.IN 6 5 5 6 4 3 4 5 2 2 4 1 4 4 1 2 2 2 5 4 1 PINBALL.OUT 5 2 1

PINBOLL

Пинболл
PINBALL

Описание
Поле в Pinball представляет собой прямоугольник без стенок, состоящий из n×m квадратных клеток (n клеток по вертикали, m клеток по горизонтали). Клетки по вертикали нумеруются сверху вниз, по горизонтали - слева направо. В каждой клетке можно установить одну отражающую пластинку в одном из двух положений: в положении 1 - от левого верхнего угла к правому нижнему или в положении 2 - от левого нижнего к правому верхнему. Летящий шарик при столкновении с пластинкой изменяет свою траекторию, при этом угол падения шарика всегда равен углу отражения и составляет 45° (см. рисунок)

На границе прямоугольника заданы две точки А и В, являющиеся серединами сторон некоторых клеток поля. Пластинки расставляются таким образом, чтобы шарик, запущенный из точки А, попал в точку В. При этом шарик начинает движение внутрь поля перпендикулярно стороне клетки, на которой находится точка А

Изначально на поле были расставлены k пластинок таким образом, чтобы шарик попал из точки А в точку В. После этого одну из пластинок удалили. Необходимо определить, куда и как можно поставить удаленную пластинку, чтобы шарик, выпущенный из точки А, попал в точку В. При этом требуется, чтобы длина пути шарика была минимальной. Пластинку нужно поставить на некоторую свободную клетку даже в том случае, если шарик попадает в точку В и без нее.

Задача
Требуется написать программу PINBALL (ограничение по памяти 64 мегабайта), устанавливающую пластинку таким образом, чтобы шарик попадал из точки А в точку В и длина его пути была минимальна.

Формат входных данных
Первая строка входного файла PINBALL.IN содержит три числа: n,m (1<=n,m<=1000) и k, где k - общее количество пластинок, которые были исходно расставлены. Во второй строке указываются номера клетки по вертикали и по горизонтали, на границе которой лежит точка А, и номер стороны, на которой она находится. Стороны клетки пронумерованы целыми числами от 1 до 4, при этом верхней стороне присвоен номер 1, далее по часовой стрелке нумеруются остальные стороны. Третья строка содержит описание точки В в том же формате.

Следующие k-1 строк описывают пластинки, оставшиеся на поле. В каждой строке записаны по три числа: первое - номер клетки по вертикали, второе - номер клетки по горизонтали, третье - положение пластинки в клетке (число 1 или 2).

Формат выходных данных
Выходной файл PINBALL.OUT должен содержать три числа: номера клетки, в которую следует поставить пластинку, по вертикали и горизонтали и ее положение. Если решений несколько, выведите любое.

Например:

PINBALL.IN
6 5 5
6 4 3
4 5 2
2 4 1
4 4 1
2 2 2
5 4 1

PINBALL.OUT
5 2 1