CODEWITHSUNDEEP
calgorithm
CDT
CDT

Reputation: 10661

How to determine the max number of points on the same line?

Given: a lot of points each with a unique coordinate (xi,yi)

Output: Max number of points on the same line

This is my method:

for i=1..n
    for j=i..n
        get the line determined by point[i] and point[j]
        for k=1..n
            check if point[k] is on this line

But it seems this method takes too much time and always exceeds the time limit on the OJ system.

Upvotes: 1

Views: 283

Answers (2)

Konsol Labapen
Konsol Labapen

Reputation: 2434

I have not implemented this, but you might be able to do it in O(n).

  • Use a hashmap to store the points by their polar angles: Map<Double,List<Point>>, where Double is the angle

  • Then iterate the map, tracking the List<Point> with the max length. That list would contain the result.

Play with that. It looks like it should work.

Upvotes: 0

songlj
songlj

Reputation: 927

iterate each point, calculate the polar angle for each other point, sort the polar angle

this cost O(n^2*lgn)

Upvotes: 3

Related Questions