Max Points on a Line

犯的错：双层for循环，max只用来记录内层循环里 点的个数，在外层循环里才是记录最后返回结果。另外 嵌套map注意

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

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

参照leetcode大神的解法：https://leetcode.com/problems/max-points-on-a-line/discuss/47113/A-java-solution-with-notes

运用最大公约数来解决求斜率的除法中小数不精确的问题

用了嵌套map的方法，把对应两点的x距离，和y距离分别作为嵌套map的key存储起来，注意这里的x和y是剔除了最大公约数以后的，也就是说，同一条线上的两个点经过剔除最大公约数的操作后，x，和y应该是相同的，存入map后，最里层map的value就是最外层遍历当前的点和其后面所有点在同一条线的个数。注意overlap的数目，overlap也算是在同一条线

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class Solution {
    public int maxPoints(Point[] points) {
        if(points == null || points.length == 0){
            return 0;
        }
        
        if(points.length <= 2)
            return points.length;
        
        HashMap<Integer,HashMap<Integer,Integer>> map = new HashMap<Integer,HashMap<Integer,Integer>>();
        int result = 0;
        for(int i = 0; i < points.length; i++){
            map.clear();
            int overlap = 0, max = 0;
            for(int j = i+1; j < points.length; j++){
                int x = points[j].x-points[i].x;
                int y = points[j].y-points[i].y;
                
                if(x == 0 && y == 0){
                    overlap++;
                    continue;
                }
                
                int gcd = getGCD(x,y);
                
                if(gcd != 0){
                    x /=gcd;
                    y /= gcd;
                }
                
                if(map.containsKey(x)){
                    if(map.get(x).containsKey(y)){
                        map.get(x).put(y,map.get(x).get(y)+1);
                    }else{
                       map.get(x).put(y,1);
                    }
                }else{
                     HashMap<Integer,Integer> subMap = new HashMap<>();
                        
                        subMap.put(y,1);
                        map.put(x,subMap);
                }
                
                max = Math.max(max,map.get(x).get(y));
            }
            
            result = Math.max(result,max+overlap+1);
        }
        
        return result;
    }
    
    public int getGCD(int x,int y){
        if(y == 0)
            return x;
        else return getGCD(y,x%y);
    }
}