【问题】

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

【思路】

对每一个点，分别计算这个点和其他所有点构成的斜率，具有相同斜率最多的点所构成的直线，就是具有最多点的直线。

【代码】

class Point:
	def __init__(self, a=0, b=0):
		self.x = a
		self.y = b

class Solution:
	# @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
    	length = len(points)
    	if length < 3:
    		return length
    	res = -1
    	for i in xrange(length):
    		slope = {'inf': 0}
    		samePointNum = 1
    		for j in xrange(length):
    			if i == j:
    				continue
    			elif points[i].x == points[j].x and points[i].y != points[j].y:
    				slope['inf'] +=1
    			elif points[i].x != points[j].x:
    				k = 1.0 * (points[j].y - points[i].y) / (points[j].x - points[i].x)
    				slope[k] = 1 if k not in slope.keys() else slope[k] + 1
    			else:
    				samePointNum += 1
    		res = max(res, max(slope.values()) + samePointNum)
    	return res
		

Max Points on a Line (Python),布布扣,bubuko.com

Max Points on a Line (Python)