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

Max points on a line
Автор silent__killer1, история, 5 лет назад, По-английски

Question — You are given a array of 2d coordinates , you need to find out the maximum points lie on a line. where the array length is n<=100000 I am googling alot but i found the answer only when n<=1000 which will be done in o(n^2) . Can anyone share their approach for when n<=100000. Thankyou…

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

»
5 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Sort 2d coordinates, and then find the maximum length of subarray with equal x or y coordinates.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    That's not correct at all. If we have lines (1, 2) and (3, 4), your answer is one. However, there is a line passing through every two points.

    → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Not always. For example, if n = 3 and points are (1,1),(2,2),(3,3). Correct answer is 3, your answer is 1

    → Ответить
»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

See this blog (section "Radial sweep").

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you share link of problem? I doubt that it can be done faster than O(N^2) unless approx probabilistic methods are allowed?

→ Ответить