Max Points on a Line题目描述：Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
解题思路：1.首先由这么一个O(n^3)的方法，也就是算出每条线的方程（n^2），然后判断有多少点在每条线上（N）。这个方法肯定是可行的，只是复杂度太高
2.然后想到一个O(N)的，对每一个点，分别计算这个点和其他所有点构成的斜率，具有相同斜率最多的点所构成的直线，就是具有最多点的直线。
注意的地方：1.重合的点
2.斜率不存在的点
1#Definition for a point2classPoint:3def__init__(self, a=0, b=0):4self.x =a5self.y =b67classSolution:8#@param points, a list of Points9#@return an integer10defcalcK(self,pa, pb):11t = ((pb.y - pa.y) * 1.0) / (pb.x -pa.x)12returnt1314defmaxPoints(self, points):15l =len(points)16res =017ifl <= 2:18returnl19foriinxrange(l):20same =021k ={}22k['inf'] =023forjinxrange(l):24ifpoints[j].x == points[i].xandpoints[j].y !=points[i].y:25k['inf'] += 126elifpoints[j].x == points[i].xandpoints[j].y ==points[i].y:27same +=128else:29t =self.calcK(points[j],points[i])30iftnotink.keys():31k[t] = 132else:33k[t] += 134res = max(res, max(k.values())+same)35returnres3637defmain():38points =[]39points.append(Point(0,0))40points.append(Point(1,1))41points.append(Point(1,-1))42#points.append(Point(0,0))43#points.append(Point(1,1))44#points.append(Point(0,0))45s =Solution()46PRints.maxPoints(points)474849if__name__=='__main__':50main()51