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 (x1, y1) and (x2, y2) is equal to ((y2-y1)/(x2-x1)). 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(n2).
MORE TO READ: