How to Count maximum points on same line in Python

A line contains an infinite number of points on its surface. Hence, if we are given a set point then there is a huge possibility of more than 1 point lying on the same line.  So the problem is to find or count the maximum points on the same line from a set of points.

For a given set of points lying on a 2-D plane. Out of these points, only those pairs of points will lie on the same line which has the same slope. The slope between two points (x₁, y₁) and (x₂, y₂) is equal to ((y₂-y₁)/(x₂-x₁)).  So for every possible pair, we will check whether the slope is equal or not. If equal we will keep the count of the number of pairs having that slope. This count will give us the maximum points on same line.

Example:

Points: [(-1, 0), (0, 1), (1, 2), (3, 3), (3, 5), (7,8),(9,8),(8,7)]
Maximum points on same line: 4
                                       [(-1,0), (0, 1), (1, 2), (7,8)]

Code: Count maximum points on the same line in Python

def Points(p):
    n=len(p)
#if points are less than or equal to two they will always be a single line
    if n<=2:
        return n
    cm=0#for storing maximum after every iteration
    #loop for finding slope of each point w.r.t all other points
    for x in p:
        D={}#new dictionary to store slope and respective number of time every new iteration
        cmax=0#max of 1 particular iteration
        d=0#number of duplicates
        #to make pair
        for y in p:
            a=(y[1]-x[1])
            b=(y[0]-x[0])
            #both points are same that is duplicate points
            if (a==0 and b==0):
               d=d+1 
            else:
                #case when line formed is vertical
                if b==0:
                    s='Infinite_slope'
                #finding slope for all other cases
                else:
                    s=a/b
                #updating the number for respetive slope
                D[s]=1+D.get(s,0)
                #updating max number
                cmax=max(cmax,D[s])
        #getting the required number
        cm=max(cm,cmax+d)
    return cm 

# Driver code 
p = [(-1, 0), (0, 1), (1, 2), (3, 3), (3, 5), (7,8),(9,8),(8,7)] 
print("Maximum number of points on same line:",end='')
print(Points(p)) 
print("BY YATHARTH JAIN")

OUTPUT:

Maximum number of points on same line:4
BY YATHARTH JAIN

The running time complexity of the above code is O(n²).

MORE TO READ:

1. How to draw line using coordinates in Python
2. Count maximum points on same line in C++