# 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-x)
b=(y-x)
#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).