Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

silent__killer1's blog

Max points on a line
By silent__killer1, history, 7 years ago, In English

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…

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

Comments Comments (7)
| Write comment?
»
7 years ago, hide # |
 
Vote: I like it -12 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
7 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

See this blog (section "Radial sweep").

→ Reply
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply