There are n points in 2d space with they (x,y) co-ordinates. Find the maximum set of points that are collinear?
PS: hard one if you want to be under cubic complexity. It is what you should expect for 1/11/11 -- those are some sort of segments where collinear points can lie.
What about this: take point p, sort others respect to the angle around p (n log n) and scan and find largest subsequence (n). So total cost is O(n^2 log n).
ReplyDeleteMaybe it can be done even better ...