Очки на решетке

Question

Я получил этот вопрос на собеседовании по кодированию.

Ханна движется в решетке, где каждая точка может быть представлена ​​парой целых чисел. Она движется из точки А в точку В, затем поворачивает на 90 градусов вправо и начинает двигаться, пока не достигнет первой точки на решетке. Найти точку, до которой она дойдет? По сути, проблема сводится к тому, чтобы найти первую точку, где перпендикуляр к линии будет пересекаться. Может ли кто-нибудь предоставить псевдокод или фрагменты кода того, как я могу решить эту проблему?

Answer 1

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

Пусть (dx, dy) = (Bx, By) - (Ax, Ay) , вектор из точки A в точку B .

Мы можем повернуть это на 90 градусов, чтобы получить (dy, -dx) .

После того, как Ханна повернет направо на B , она направится вдоль этого повернутого вектора в направлении (Bx + dy, By-dx)

Поскольку она движется по прямой линии, ее вектор из B будет следовать (t.dy, -t.dx) и попадет в другую точку решетки, когда оба эти компонента являются целыми числами, то есть ..

Она достигнет другой точки решетки в: (Bx + dy / GCD (| dx |, | dy |), By - dx / GCD (| dx |, | dy |))