OJ Board

There are many points in x, y coordinates and I'd like to get a straight line which contains as many points as possible..
I only have O(n^3) solution.. Is there any more efficient way..?
Thanks..

O(n^2 log n) is possible (and even expected O(n^2) with hashtables.)
Read topics on this board on problem 270.

I think that you can get to worst-case O(N^2) using point-line duality. Transform the problem into "given N different lines, find the largest subset that pass through the same point", and then traverse the whole plane subdivision given by the N lines, and look for a vertex with the largest degree.

Of course, this is just a theoretical result, not what I'd (want to) implement. mf's suggestions are way easier to implement.

Thanks..~ I finally figured that out ..

You can hash the n^2 intersection points in the dual plane, and get a easier O(n^2) solution but it's O(n^2) memory.

Achtung!!