Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example 1:
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
Example 2:
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
My code:
# Definition for a point.
# class Point(object):
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b
class Solution(object):
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
length=len(points)
if len(points)==0:
return 0
result=1
for i in range(length-1):
same=0
tmp_dict={}
tmp_dict['g']=1
point1=points[i]
for j in range(i+1,length):
point2=points[j]
if point1.x==point2.x and point1.y==point2.y:
same+=1
continue
if point1.x==point2.x:
slope='y'
else:
slope1=(point1.y-point2.y)
slope2=(point1.x-point2.x)
if slope1!=0:
common=self.hcf(slope1,slope2)
slope1=int(slope1/(common))
slope2=int(slope2/(common))
if point1.x>point2.x:
slope1=-slope1
slope2=-slope2
slope=str(slope1)+','+str(slope2)
if slope1==0:
slope='0'
if slope not in tmp_dict.keys():
tmp_dict[slope]=1
tmp_dict[slope]+=1
result=max(result,max(tmp_dict.values())+same)
print(tmp_dict)
return result
def hcf(self,x, y):
x=abs(x)
y=abs(y)
if x < y:
tmp=x
x=y
y=tmp
if x%y==0:
return y
else:
return self.hcf(y,x%y)
Solution: https://leetcode.com/problems/max-points-on-a-line/