Just an idea for each pair of points, compute the slope and the y-intercept. Then sort these pairs lexicographically and find the longest run and its corresponding pairs. Of course you will need to work around degenerate cases like vertical lines. But those will not dominate the runtime, which is O(n^2).
Just an idea
ReplyDeletefor each pair of points, compute the slope and the y-intercept. Then sort these pairs lexicographically and find the longest run and its corresponding pairs. Of course you will need to work around degenerate cases like vertical lines. But those will not dominate the runtime, which is O(n^2).