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

 

不难理解 但是很繁琐。

y0/x0 来记录每两点间的斜率

用一个双重map，第一层记录出现过的x0值，第二层记录出现过的y0值，最后的value记录出现的次数。

/**
 * 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) return 0;
        if(points.length <= 2) return points.length;
        
        Map<Integer, Map<Integer,Integer>> map = new HashMap<>();
        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 x0 = points[i].x - points[j].x;
                int y0 = points[i].y - points[j].y;
                if(x0 == 0 && y0 == 0){
                    overlap++;
                    continue;
                }
                int gcd = generateGCD(x0, y0);
                if(gcd != 0){
                    x0 /= gcd;
                    y0 /= gcd;
                }
                
                if(map.containsKey(x0)) {
                    if(map.get(x0).containsKey(y0)){
                        map.get(x0).put(y0, map.get(x0).get(y0)+1);
                    }else{
                        map.get(x0).put(y0, 1);
                    }
                }else{
                    Map<Integer, Integer> m = new HashMap<>();
                    m.put(y0, 1);
                    map.put(x0, m);
                }
                max = Math.max(max, map.get(x0).get(y0));
            }
            result = Math.max(result, max + overlap + 1);
        }
        return result;
    }
    
    //求最大公约数
    public int generateGCD(int a, int b){
        if(b == 0) return a;
        else return generateGCD(b, a%b);
    }
}