Given two lines on a plane, how to find integer points closest to their intersection?

Question

I can't solve it:

You are given 8 integers:

• A, B, C representing a line on a plane with equation Ax + By = 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.

Update 2: Difficult case - when lines are almost parallel - is the heart of the problem

Update 3: Author of the problem states that the solution is linear O(n) algorithm. Where n is the size of the input (in bits). Ie: n = log(A) + log(B) + ... + log(y)
But I still can't solve it.

Please state complexities of published algorithms (even if they are exponential).

Answer 1

alt text http://imagebin.ca/img/yhFOHb.png

Diagram

After you find intersection of lines L1:Ax+By=C and L2:ax+by=c i.e. point A(x1,y1).

Define two more lines y = ceil(y1) and y = floor(y1) parallel to X-axis and find their intersection with L1 and L2 i.e. Points B(x2,y2) and C(x3,y3).

Then point you require is D or E whichever is closer to point A. Similar procedure applies to other parts of the plane.

D ( ceil(x2), ceil(y1)  ) E ( ceil(x3), floor(y1) )