Edit Question - KnowledgeHub

Title Body

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. 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).

Tags (comma-separated) Cancel