### pks18's blog

By pks18, history, 3 years ago,

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.

• +9

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   0 Move ahead. wrong approach here.
•  » » 3 years ago, # ^ |   +3 "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?
•  » » » 3 years ago, # ^ |   0 Shit. how stupid i am. I forget that two parallel lines have same slope. thanks for correction.
•  » » 3 years ago, # ^ |   +3 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).
•  » » » 3 years ago, # ^ |   0 yeah. seems it will work.