title: Find all collinear points in a given set
body: <p>This is an <a href="http://www.glassdoor.com/Interview/Phone-Interview-i-Find-the-number-of-inversions-in-an-array-describe-and-code-ii-Find-collinear-points-in-a-given-set-QTN_129352.htm" rel="noreferrer">interview question</a>: "Find all collinear points in a given set".</p>
  
  <p>As I understand, they ask to print out the points, which lie in the same line (and every two points are always collinear). I would suggest the following.</p>
  
  <ol>
  <li>Let's introduce two types <code>Line</code> (pair of doubles) and <code>Point</code> (pair of integers).</li>
  <li>Create a multimap : <code>HashMap&lt;Line, List&lt;Point&gt;)</code></li>
  <li>Loop over all pairs of points and for each pair: calculate the <code>Line</code> connecting the points and add the line with those points to the multimap.</li>
  </ol>
  
  <p>Finally, the multimap contains the lines as the keys and a list collinear points for each line as its value.</p>
  
  <p>The complexity is O(N^2). Does it make sense ? Are there better solutions ?   </p>