Given two lines on a plane, how to find integer points closest to their intersection?
- by Lukasz Lew
I can't solve it:
You are given 8 integers:
A, B, C representing a line on a plane with equation A*x + B*y = C
a, b, c representing another line
x, y representing a point on a plane
The two lines are not parallel therefore divide plane into 4 pieces.
Point (x, y) lies inside of one these pieces.
Problem:
Write a fast algorithm that will find a point with integer coordinates in the same piece as (x,y) that is closest to the cross point of the two given lines.
Note:
This is not a homework, this is old Euler-type task that I have absolutely no idea how to approach.
Update:
You can assume that the 8 numbers on input are 32-bit signed integers.
But you cannot assume that the solution will be 32 bit.
