Lamentis's blog

By Lamentis, history, 2 years ago, In English

Q) Given a 2D array of size n that represents the x and y coordinates([x,y]), find the number of collinear triplets.If collinear triplets>1e9, then return -1.

N<=1000

----------------------------------------------- This question came in yesterday's Microsoft OA. I was not able to come up with an efficient solution and ultimately wrote an O(n^3) solution using the idea that the area of triangle formed by three collinear points is 0.

Please suggest an efficient solution.

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

here is a general idea

for each point(call it pi), traverse other points, calculate slope and numbers of each slope, store in a (hash)map. something like map<pair<int, int>, int>.

then for a desired triplet, we assume pi is fixed, and for every pair(slope and count) in map, we can add all $$$\binom{count}{2} $$$ to the answer.

for some implement detail, maybe you'd better sort the point first, and take care of computing slope

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    The Problem here is its difficult to create map for slopes since slopes are double valued, so can't be used as keys. So for that create a structure, that stores them in pair format preferably({num, den}), by dividing both num and den by their gcd.

    Basically for every point you have a map that has {slope, cnt}. As stated add C(cnt, 2) to the answer, and the final answer will be ans/3, as every triplet is being counted thrice.

    Also take care of the case when num/den becomes 0 in slope, in that case store intercepts correctly.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      yes of course we won't store slope as floating point, that's why i say "map<pair<int, int>, int>" . sorry for other parts, maybe a bit of misleading.