Блог пользователя MarioYC

Maximum number of points on a line
Автор MarioYC, 12 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
Nice problem. Dont you know constraints of n?
→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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).

→ Ответить