Q:

Finding all points that are located in one line in 2D coordinate system

I have an array of points. Each point has two members - x and y.
I want to get any 3 points and check, are they located in single line in 2D coordinate system.
For example - 1x2, 2x3, 5x6:

If yes, I want to search for another point in my array which is located in that line (line has no start and no end). And so on, while I didn't check all remained points.
Then, I want to check next combination of 3 points and repeat while all 3-points permutations are no checked. For every of that permutations I want to tell how many points are located in single line (0 - if these 3 points are no located in single line, 3 - if they are, 4 - if they are and that's other point which also is located in that line, etc.). Is there any effective algorithm that can do it in complexity equal or less than O(n3)?

A:

For two points you can calculate the slope and the y intercept. If two different segments are part of the same line they will have the same slope and the same y intercept. If they have the same slope but different y intercepts they are parallel.
The only issue is when the line is vertical, the slope is infinite and the there is no y intercept, unless it is the line x=0.
Calculate all the pairs of points, and then cluster them by slope and intercept.

