I got this question somewhere:
Hanna moves in a lattice where every point can be represented by a pair of integers. She moves from point A to point B and then takes a turn 90 degrees right and starts moving till she reaches the first point on the lattice. Find what's the point she would reach? In essence the problem boils down to finding the first point where the perpendicular to a line will intersect.
I did find one solution on stack overflow but can't understand it. Can someone please explain me the following solution:
Let (dx,dy) = (Bx,By)-(Ax,Ay), the vector from point A to point B.
We can rotate this by 90 degrees to give (dy,-dx).
After hanna turns right at B, she will head out along that rotated vector toward (Bx+dy,By-dx)
Since she is moving in a straight line, her vector from B will follow (t.dy,-t.dx), and will hit another lattice point when both of those components are integers, i.e...
She will hit another lattice point at: (Bx + dy/GCD(|dx|,|dy|), By - dx/GCD(|dx|,|dy|) )
Hanna moves in a lattice where every point can be represented by a pair of integers. She moves from point A to point B and then takes a turn 90 degrees right and starts moving till she reaches the first point on the lattice. Find what's the point she would reach? In essence the problem boils down to finding the first point where the perpendicular to a line will intersect.
I did find one solution on stack overflow but can't understand it. Can someone please explain me the following solution:
Let (dx,dy) = (Bx,By)-(Ax,Ay), the vector from point A to point B.
We can rotate this by 90 degrees to give (dy,-dx).
After hanna turns right at B, she will head out along that rotated vector toward (Bx+dy,By-dx)
Since she is moving in a straight line, her vector from B will follow (t.dy,-t.dx), and will hit another lattice point when both of those components are integers, i.e...
She will hit another lattice point at: (Bx + dy/GCD(|dx|,|dy|), By - dx/GCD(|dx|,|dy|) )