title: Given two lines on a plane, how to find integer points closest to their intersection?
body: <p>I can't solve it:</p>
  
  <p>You are given 8 integers:</p>
  
  <ul>
  <li>A, B, C representing a line on a plane with equation A<em>x + B</em>y = C </li>
  <li>a, b, c representing another line</li>
  <li>x, y representing a point on a plane</li>
  </ul>
  
  <p>The two lines are not parallel therefore divide plane into 4 pieces.
  Point (x, y) lies inside of one these pieces.</p>
  
  <p>Problem:<br>
  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.</p>
  
  <p>Note:<br>
  This is not a homework, this is old <a href="http://projecteuler.net/" rel="nofollow noreferrer">Euler</a>-type task that I have absolutely no idea how to approach.</p>
  
  <p><strong>Update:</strong>
  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.</p>
  
  <p><strong>Update 2:</strong>
  Difficult case - when lines are almost parallel - is the heart of the problem</p>
  
  <p><strong>Update 3:</strong>
  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)<br>
  But I still can't solve it.  </p>
  
  <p>Please state complexities of published algorithms (even if they are exponential).</p>