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

    Example 1:

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

    Example 2:

    1. Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
    2. Output: 4
    3. Explanation:
    4. ^
    5. |
    6. |  o
    7. |     o        o
    8. |        o
    9. |  o        o
    10. +------------------->
    11. 0  1  2  3  4  5  6

    NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

    题意

    给定n个二维点，返回最大共线点数目。

    思路

    固定一个点，以该点为基准，计算其他所有点到该点的斜率，斜率相同则说明共线，斜率信息用HashMap记录。更换基准点重复上述步骤。有以下几点要注意：

    1. 因为本题允许相同点的存在，所以要统计每一个基准点相同点的个数，之后要加到共线点数结果中；如果最后HashMap没有记录，说明只存在相同点；
    2. 因为double的精度不够，在部分case会出现判断错误(虽然用斜率的倒数作为key可以AC)，所以HashMap使用String来作为key，具体方法为将斜率用分数形式表示，约分后转化为字符串作为key。

    代码实现

    1. class Solution {
    2.     public int maxPoints(int[][] points) {
    3.         if (points.length <= 2) {
    4.             return points.length;
    5.         }
    7.         int maxCount = 0;
    8.         Map<String, Integer> slopes = new HashMap<>();
    9.         for (int i = 0; i < points.length; i++) {
    10.             int baseX = points[i][0], baseY = points[i][1];
    11.             int sameCount = 1;            // 统计重复基准点个数，初始为1指自身
    12.             int maxTemp = 0;            // 记录当前基准点得到的最大共线点数
    13.             slopes.clear();                // 注意每次更换基准点都要清空HashMap
    15.             for (int j = i + 1; j < points.length; j++) {
    16.                 int curX = points[j][0], curY = points[j][1];
    18.                 // 重复基准点处理
    19.                 if (curX == baseX && curY == baseY) {
    20.                     sameCount++;
    21.                     continue;
    22.                 }
    24.                 // 找到最大公约数，并进行约分，并将斜率转化为分数形式
    25.                 int gcd = gcd(curX - baseX, curY - baseY);
    26.                 String slope = (curX - baseX) / gcd + "/" + (curY - baseY) / gcd;
    28.                 // 更新HashMap以及当前最大共线点数
    29.                 slopes.put(slope, 1 + (slopes.containsKey(slope) ? slopes.get(slope) : 0));
    30.                 maxTemp = Math.max(maxTemp, slopes.get(slope));
    31.             }
    33.             maxCount = Math.max(maxCount, maxTemp + sameCount);
    34.         }
    36.         return maxCount;
    37.     }
    39.     private int gcd(int a, int b) {
    40.         return b == 0 ? a : gcd(b, a % b);
    41.     }
    42. }