149. 直线上最多的点数

Problem: 149. 直线上最多的点数

知识点

不要有HashMap全局只能有一个的惯性思维，例如本题就需要把哈希表定义为从某一点出发的每个斜率个数。

浮点数除法可能会有精度问题，例如0除以不同的数不一定都得0，至少需要在分母0也做一个特判，亦或使用分数表示或者叉积表示，叉积等于0两个直线共线。

Code

class Solution {
    double INF = 1000000.0;
    public int maxPoints(int[][] points) {
        int ans = 0;
        int n = points.length;
        if (n < 2) return n;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double rate1;
                int sum = 2;
                if (points[i][1] - points[j][1] == 0) rate1 = INF;
                else rate1 = (double)(points[i][1] - points[j][1]) / (points[i][0] - points[j][0]);
                for (int k = 0; k < n; k++) {
                    if (k != j && k != i) {
                        double rate2;
                        if (points[i][1] - points[k][1] == 0) rate2 = INF;
                        else rate2 = (double)(points[i][1] - points[k][1])/ (points[i][0] - points[k][0]);
                        if (rate1 == rate2) sum++;
                    }
                }
                ans = Math.max(sum, ans);
            }
        }
        return ans;
    }
}