Given a set $S$ of points $p_1,..,p_2$ give the most efficient algorithm for determining if any 3 points of the set are collinear.
The problem is I started with general definition but I cannot continue to actually solving the problem.
What can we say about collinear points in general, 3 points $a,b,c$ are collinear if the distance $d(a,c) = d(a,b)+d(b,c)$ in the case when $b$ is between $a$ and $c$.
The naive approach has $O(n(n-1)(n-2))=O(n^3)$ time complexity.
How to solve this problem, what should be the next step?