Задача №1749. Бильярд
Есть прямоугольный стол для игры в бильярд размером \(N\)x\(M\). Стол расположен в системе координат так, что его углы находятся в точках с координатами (0,0), (\(N\),0), (\(N\),\(M\)), (\(M\),0).
На столе лежат черный и белый шары. Игрок ударяет по черному шару, задавая ударом направление его движения. Шар летит в заданном направлении, отскакивая от стенок стола по закону отражения. Когда черный шар ударяет по белому шару, то черный шар останавливается, а белый начинает двигаться в том направлении, куда летел в момент удара черный. После этого белому шару запрещается ударять черный шар.
Задача игрока — загнать белый шар в одну из луз, расположенных в углах стола. При этом до попадания в лузу черный и белый шары должны удариться о стенки стола суммарно как можно меньше раз, но не более \(K\) раз.
Сначала вводятся размеры стола \(N\) и \(M\) (3≤\(N\)≤1000, 3≤\(M\)≤1000). Далее записано число K (0≤K≤200). Затем записано две пары чисел \(X_1\), \(Y_1\), \(X_2\), \(Y_2\) – начальные координаты черного шара и начальные координаты белого шара (1≤\(X_1\)≤\(N\)–1, 1≤\(Y_1\)≤\(M\)–1, 1≤\(X_2\)≤\(N\)–1, 1≤\(Y_2\)≤\(M\)–1). Гарантируется, что начальные положения шаров не совпадают, и изначально шары находятся строго внутри стола.
Все числа целые.
Выведите минимальное суммарное количество ударов черного и белого шаров о стенки стола до попадания белого шара в лузу. Если попасть белым шаром в лузу, сделав не более K ударов, невозможно, выведите –1 (минус один).
4 4 3 2 1 2 3
1
4 4 200 1 1 1 3
-1
5 4 3 4 1 4 3
3
5 4 0 3 2 4 3
0