動機

同樣的點好可怕

Problem

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

 

Example 1:

Input: points = [[1,1],[2,2],[3,3]]Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]Output: 4

 

Constraints:

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -104 <= xi, yi <= 104
  • All the points are unique.

Sol

先依照x與y軸排序，再從每個點去看所有右手邊的點，統計所有斜率

這裡有兩個重點

  • 斜率不能用float存，不然可能算出來會不一樣，所以要用pair
  • 看所有右手邊的點還是會重疊，所以每次看完要去更新大表看有沒有比他多

還有一個很可怕的，同樣的點可以出現很多次，所以在計算斜率有多少點時，要加上這個點出現的次數

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 1:
            return len(points)
        
        points = [(p[0],p[1]) for p in points]
        points = Counter(points)
        global_cnt = {None: max(points.values())}
        ps = list(points.keys())
        ps.sort(key=lambda x: (x[0],x[1]))
        for i in range(len(ps)):
            local_cnt = {}
            for j in range(i+1,len(ps)):
                a, b = ps[j][1]-ps[i][1], ps[j][0]-ps[i][0]
                c = max(1,math.gcd(abs(a),abs(b)))
                slope = (a//c, b//c)
                if slope not in local_cnt:
                    local_cnt[slope] = points[ps[j]]
                else:
                    local_cnt[slope] += points[ps[j]]
                #print((a//c, b//c), ps[i], ps[j])
            for k in local_cnt:
                global_cnt[k] = max(global_cnt.get(k,0), local_cnt[k]+ points[ps[i]]) 
        #print(global_cnt)
        return max(global_cnt.values())