Post
by junbin » Sun Jan 04, 2004 9:57 am
Can either of you explain your algorithm or give more hints?
Here is my take:
1) Hash all coordinates by x and y values to arrive at 2 hash tables, one for x and one for y values.
2) Take the hash table (either x or y) with the least hashes.
3) Compare all coorindates in a hash with all coordinates OUTSIDE the hash (since every coordinate in a hash forms either a vertical or a horizontal line, so that is a trivial solution).
4) To see if three points a, b and c are collinear, (a is in the hash, b and c are outside the hash), simply compare the gradients of a-b and a-c.
My algorithm to compare the gradients is simply for all points outside a hash, calculate the gradient with a point inside the hash. If any two gradients are simliar, then the 3 points are collinear.
This, however, is a O(n^3) algorithm and even when I hash the gradients for each point, I get time limit exceeded.
Am I on the right track here, or am I hashing the wrong things altogether?