pks18's blog

Number of lines passing through atleast three points
By pks18, history, 4 years ago, In English

The question is as follows:-

We are given n coordinates in the form of (xi,yi) for ith coordinate. Then we need to find the number of lines passing through atleast three points?

I have a feeling it would be n^3 approach with checking of slopes, but I am not able to boil down it to code. I am particularly facing problem in the case when 4 or more points fall in the same line. How to stop double counting?

Help would would be greatly appreciated.

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

Comments Comments (5)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Move ahead. wrong approach here.

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

    "Now if a slope appears more than once(by that i mean if two or more pairs has same slope) than there must be a line that passes through these(atleast 3) points". I think it is not necessarily true because we may have parallel lines. Am I right?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Shit. how stupid i am. I forget that two parallel lines have same slope. thanks for correction.

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

    But I think it can be implemented if we maintain a pair of slope and y-intercept. And resulting time-complexity would be O(n^2logn).

    → Reply