149.md

149. 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.

my thoughts:

1. find the line funcs, and count points on each line.
y = a*x + b this will cause two float nums and b is calculated baseed on a. python does not handle it very well. 

2. iterate the points, pin down the first point and scan the later ones for slope (edge cases: same point, same x coord) update the max points on a line as we move first point. still python does not handle the float point num very well. specifically:
[[0,0],[94911151,94911150],[94911152,94911151]] will be regarded as on the same line.

* form other ppl's solution:
import numpy as np;  times the float num by np.longdouble(1) to increase accuracy.

my solution:

**********192ms
# Definition for a point.
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b
import numpy as np
class Solution:
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        res = 0
        l = len(points)
        if l < 3:
            return l
        
        for i in range(l-1):
            count = 1
            d_slopes = {}
            p1 = points[i]
            for j in range(i+1, l):
                p2 = points[j]
                if p1.x == p2.x and p1.y == p2.y:
                    count += 1
                    continue
                elif p1.x == p2.x:
                    slope = '#'
                else:
                    slope = (p1.y - p2.y)*np.longdouble(1)/(p1.x - p2.x)
                d_slopes[slope] = d_slopes.get(slope, 0) + 1
            count += max(d_slopes.values()) if d_slopes else 0
            print(count, d_slopes.items())
            res = max(res, count)
        
        return res

my comments:

from other ppl's solution:

1. more python libraries, 79ms:
# Definition for a point.
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

import itertools
import fractions
import math

class Solution:
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        result = 0
        for i, p1 in enumerate(points):
            counts = collections.defaultdict(int)
            counts['max_int'] = 1
            #
            j = 0
            same = 0
            for j, p2 in enumerate(itertools.islice(points, i)):
                p2 = points[j]
                dx, dy = p2.x - p1.x, p2.y - p1.y

                if dx == 0 and dy == 0:
                    same += 1
                    continue
                elif dx == 0:
                    slope = 'max_int'
                else:
                    slope = dy/dx
                    
                if slope not in counts:
                    counts[slope] = 1
                counts[slope] += 1
            
            local_max = same + max(counts.values())
            result = max(result, local_max)
        return result