149.Max Points on a Line

https://leetcode.com/problems/max-points-on-a-line/discuss/47113/

1. 如何判断共线?

两点成一直线，所以两点没有共线不共线之说。对于点p1(x1, y1)，p2(x2, y2)，p3(x3, y3)来说，共线的条件是p1-p2连线的斜率与p1-p3连线的斜率相同，即

(y2-y1)/(x2-x1) = (y3-y1)/(x3-x1)

所以对共线的n点，其中任意两点连线的斜率相同。

1. 如何判断最多的共线点?

对于每个点p出发，计算该点到所有其他点qi的斜率，对每个斜率统计有多少个点符合。其中最多的个数加1（出发点本身）即为最多的共线点。

1. 特殊情况

当x1 = x2，y1!=y2时，为垂直连线。计算斜率时分母为0会出错。

当x1 = x2，y1 = y2时，两点重合。则(x2, y2)和所有(x1, y1)的连线共线。
由于通过斜率来判断共线需要用到除法，而用double表示的双精度小数在有的系统里不一定准确，为了更加精确无误的计算共线，我们应当避免除法，从而避免无线不循环小数的出现，那么怎么办呢，我们把除数和被除数都保存下来，不做除法，但是我们要让这两数分别除以它们的最大公约数，这样例如8和4，4和2，2和1，这三组商相同的数就都会存到一个映射里面，同样也能实现我们的目标，而求GCD的函数如果用递归来写那么一行就搞定了

Greatest Common Divisor(GCD)

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
/*
     *  A line is determined by two factors,say y=ax+b
     *  
     *  If two points(x1,y1) (x2,y2) are on the same line(Of course). 

     *  Consider the gap between two points.

     *  We have (y2-y1)=a(x2-x1),a=(y2-y1)/(x2-x1) a is a rational, b is canceled since b is a constant

     *  If a third point (x3,y3) are on the same line. So we must have y3=ax3+b

     *  Thus,(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a

     *  Since a is a rational, there exists y0 and x0, y0/x0=(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a

     *  So we can use y0&x0 to track a line;
     */
class Solution {
    public int maxPoints(Point[] points) {
        if(points == null)
            return 0;
        if(points.length <= 2)
            return points.length;
        //Key1: x, Key2: y, Val: # of line with slope x, y;
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        int ans = 0;
        for(int i = 0; i < points.length; i++){
            map.clear();
            int currentMax = 0;
            int overlap = 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{
                        //Two points in a line
                        map.get(x).put(y, 1);
                    }
                }
                else{
                    Map<Integer, Integer> tmpMap = new HashMap<>();
                    tmpMap.put(y, 1);
                    map.put(x, tmpMap);
                }
                currentMax = Math.max(currentMax, map.get(x).get(y));
            }
            ans = Math.max(ans, currentMax + overlap + 1);          
        }
        return ans;
    }
    private int getGCD(int a, int b){
        if(b == 0)
            return a;
        else
            return getGCD(b, a % b);
    }
}