题目

给你一个数组 points ，其中 points[i] = [x_i, y_i] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：3

示例 2：

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

提示：

• 1 <= points.length <= 300
• points[i].length == 2
• -10⁴ <= x_i, y_i <= 10⁴
• points 中的所有点 互不相同

题解

public int maxPoints(int[][] points) {
    int length = points.length;
    // 小于3个点 肯定在一条直线
    if (length < 3) {
        return length;
    }

    int result = 0;
    for (int i = 0; i < length; i++) {
        // 相同点数量
        int same = 1;
        for (int j = i + 1; j < length; j++) {
            int count = 0;
            if (points[j][0] == points[i][0] && points[j][1] == points[i][1]) {
                // i点和j点相同 相同点数量增加
                same++;
            } else {
                // i点和j点不同 数量增加
                count++;
                // 有点A(x1, y1) B(x2, y2) C(x3, y3)
                // 三点一线公式 (x2-x1)*(y3-y1) = (x3-x1)*(y2-y1)
                // 转为long型 会溢出
                long dx1 = points[j][0] - points[i][0];
                long dy1 = points[j][1] - points[i][1];
                // 选取第三个点
                for (int k = j + 1; k < length; k++) {
                    long dx2 = points[k][0] - points[i][0];
                    long dy2 = points[k][1] - points[i][1];
                    if (dx1 * dy2 == dy1 * dx2) {
                        count++;
                    }
                }
            }
            result = Math.max(result, same + count);
        }

    }

    return result;
}