MarioYC's blog

Maximum number of points on a line
By MarioYC, 13 years ago, In English

Hi, I've solved this problem before with O(N^2 lgN) algorithm. For example: http://pastie.org/3129354

But today I got to this problem: http://www.spoj.pl/problems/CHASE/
I got TLE with O(N^2 lgN) algorithm, and a O(N^2) algorithm is mentioned in comments, could someone explain how it works.

N means the number of points given.

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it -9 Vote: I do not like it
Nice problem. Dont you know constraints of n?
→ Reply
»
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Maybe by O(N^2)-solution a hash-map solution was meant?

If you fix one point, you have to find maximum number of another points that have the same polar angle. So the problem transforms into finding the number that encountered maximum number of times among given N-1 double numbers - this can be done with hash-map (also you can try to replace double angles with pairs of integers - reduced fractions).

→ Reply