Question: https://oj.leetcode.com/problems/max-points-on-a-line/
Question Name: Max Points on a Line
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | # Definition for a point # class Point: # def __init__(self, a=0, b=0): # self.x = a # self.y = b class Solution: # @param a, an integer # @param b, an integer # @return an integer, the Greatest Common Divisor of a and b. def _getGCD(self, a, b): ''' Compute the Greatest Common Divisor of a and b. ''' if a < b: a, b = b, a if a % b != 0: return self._getGCD(b, a%b) else: return b # @param points, a list of Points # @return an integer def maxPoints(self, points): if len(points) == 0: return 0 maxCount = 1 # For a single point for index in xrange(len(points)-1): point = points[index] maxCountForThisPoint = 0 # Each to-compare point must fall into one of the following # four cases. vertical = 0 # The two points are on one vertical line. horizontal = 0 # The two points are on one horizontal line. samePos = 1 # The points are in one completely same position. # At least it has the same position as itself. slop = {} # For all the other cases. for toCmp in points[index+1:]: diffX = toCmp.x - point.x diffY = toCmp.y - point.y if diffX == 0 and diffY == 0: samePos += 1 elif diffX == 0: vertical += 1 elif diffY == 0: horizontal += 1 else: # Make sure either: # Both diffX and diffY are positive; # OR # diffX is negative while diffY positive. # So that we can get slop(-5,3) == slop(5,-3). if diffX < 0 and diffY < 0: diffX, diffY = -diffX, -diffY elif diffX < 0 or diffY < 0: diffX, diffY = -abs(diffX), abs(diffY) # Simplify the diffX and diffY. So that we could # get slop(5, 10) == slop(1,2). gcd = self._getGCD(abs(diffX), diffY) diffX //= gcd diffY //= gcd slop[(diffX, diffY)] = slop.get((diffX, diffY), 0) + 1 # Find the maximum number of points that lie on the same straight line, # which cross the current point. if len(slop) != 0: maxCountForThisPoint = max(slop.values()) maxCountForThisPoint = max(vertical, horizontal, maxCountForThisPoint) maxCountForThisPoint += samePos maxCount = max(maxCount, maxCountForThisPoint) return maxCount |