直线上最多的点数

问题描述：

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

示例 1:

输入:

 [[1,1],[2,2],[3,3]]

输出:

 3

解释:

^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

示例 2:

输入:

 [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

输出:

 4

解释:

^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

思路：

寻找以某一点为起始点的斜率，如果斜率相同的有几个点是共线的，所以遍历所有点作为起始点，计算起始点之后的点的斜率（之前的不用计算因为是重复的），放进map中，map的键是斜率，值是点的个数。主要注意两点问题：
使用double作为斜率的表达可能会因为精度问题导致不同的斜率算出的结果一样，而且注意double类型有0.0和-0.0，infinite和-infinite的差别，存入map可能会出错，所以采用分数转成字符串进行表达。分数的计算可以采用欧几里得算法算出最大公约数，然后分子分母分别除以最大公约数，拼装成字符串作为map的键。
要注意存在坐标与起始点相同的点，这样的点会造成所有共线的点数要增加，注意处理。

代码：

import java.util.*;
class Point {
    int x;
    int y;
    Point() { x = 0; y = 0; }
    Point(int a, int b) { x = a; y = b; }
}
public class Solution {
    // 欧几里得算法求最大公约数
    public int gcd(int a, int b){
        if (b == 0) return a;
        return gcd(b,a%b);
    }
    public int maxPoints(Point[] points) {
        if (points.length == 0) return 0;
        int res = 0;
        for (int i=0; i<points.length; i++){
            HashMap<String, Integer> kMap = new HashMap();
            int same = 1;// same用于保存与初始点坐标相同的点的个数（包括初始点）
            for (int j=i+1; j<points.length; j++) {
                // 坐标相同就把same++
                if (points[i].x == points[j].x &&
                        points[i].y == points[j].y) {
                    same++;
                } else {
                    int dy = points[j].y - points[i].y;
                    int dx = points[j].x - points[i].x;
                    int maxD = gcd(dx, dy);
                    // 将最简分数作为key
                    String key = dy/maxD + "/" + dx/maxD;
                    if (kMap.containsKey (key)) {
                        kMap.put(key, kMap.get(key) + 1);
                    } else {
                        kMap.put(key, 1);
                    }
                }
            }
            int count = 0;  // count统计不同斜率点的个数
            for (Map.Entry<String, Integer> entry : kMap.entrySet()){
                if (entry.getValue() > count){
                    count = entry.getValue();
                }
            }
            // res存共线点个数的最大值
            res = Math.max(res, count + same);
        }
        return res;
    }
}