Count the number of distinct collinear triplets in a set of n points in the plane.
Straightforward Algorithm:
- For every point i, we check every j and k and see if ij have the same slope and y-intercetp as jk.
- This takes O(n^3) time and constant space.
Improved Algorithm:
- For every point, we calculate its slope with every other point, store these slopes in an array, and sort the array.
- Then we check adjacent entries in the array - having the same slope implies colinearity.
- We reuse the array for next point.
- This takes O(n^2 * lg(n)) time and O(n) space.
Testing:
- In ViewPoints.c, the constant MAX_NUM_TRIPLETS at the top is the maximum size of the array that stores triplets.
- If n is large, you will need to modify this number to avoid overflow (maximum number of triplets for n is n choose 3).