wish_me's blog

Count maximum points on same line
By wish_me, history, 7 years ago, In English

Given N point on a 2D plane as pair of (x, y) co-ordinates, we need to find maximum number of point which lie on the same line.

Examples:

Input : points[] = {-1, 1}, {0, 0}, {1, 1}, {2, 2}, {3, 3}, {3, 4}

Output : 4

Then maximum number of point which lie on same

line are 4, those point are {0, 0}, {1, 1}, {2, 2}, {3, 3}

where arr.size<10^3

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

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Fix each point and calculate the slopes of all lines from this point to all other points. Find the slope with the maximum frequency. Repeat for each point.

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

Good day to you.

Well firstly, lets consider similar question "find maximum number of point which lie on the same line and contains Ith point?

So what can we do? We will fix the point and sort all remaining points by "angle". Now, all points with equal angle OR angle equal to "angle+180" lie on the same line... so well, we made it in O(NlogN) [sort]

To transfer your question to mine, simply try every possible I, making this O(N2log(N))

If this would be "too slow" or you would like to get rid of doubles, there is "similar solution" which uses "vectors" instead of doubles. As you can see, the vector (from fixed point to given point) can be "their difference" (i.e. [Xi-Xj][Yi-Yj].

Well offcourse this is not nice yet, since vectors can have different sizes. To normalize them, simply divide both X, Y by their gcd. Now you can simply bucket (lets say by a map/hash map?) all points on same half-line together. The thing which is missing is to bucket together vectors which go on oposite side. As you can see, they will be just "multiplied" by "-1" so you can always bucket SUCH vector, that has X nonnegative (and in case of 0, nonnegative Y).

Hope this helped a little bit (and I understood your problem)

Good Luck & Have Georgeous Day!

→ Reply