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.

Select a point and find all other points which has the same slope. Use a hash map to keep the same slope number.

Be care for the overlap point and same x value points.

    public int maxPoints(Point[] points) {

        if (points.length < 3) return points.length;  

        int max = 0;
        Map<Double, Integer> map = new HashMap();
        // find same slope of with a target point 
        for (int i = 0; i < points.length; i++) {
            int overlap = 1;
            for(int j = 0 ; j < points.length; j++){  
                if (i == j) continue;
                double slope = 0.0;
                // same x points, y / 0 will error
                if (points[i].x == points[j].x) { 
                    if(points[i].y == points[j].y){
                        overlap ++; continue;   
                    }
                    else slope = Integer.MAX_VALUE;  
                } else {
                    slope = 1.0 * (points[i].y - points[j].y) / (points[i].x - points[j].x);  
                }  
                map.put(slope, map.containsKey(slope) ? map.get(slope) + 1 : 1);  
            }  
            if(map.keySet().size() == 0) max = Math.max(overlap, max);
            for (double key : map.keySet()) {  
                max = Math.max(overlap + map.get(key), max);   
            }

            map.clear(); 
        }  

        return max; 
    }

def maxPoints(self,points):
    res = 0
    for p in points:
        dict = collections.defaultdict(int)
        itself = 0
        for q in points:
            x,y = q.x - p.x, q.y - p.y
            if x:
                dict[float(y)/x] += 1
            else:
                if y:
                    dict[float('inf')] += 1
                else:
                    itself += 1
        res = max(res,max(dict.values())+itself if dict.values() else itself)
    return res