Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
样例：如：[[84,250],[0,0],[1,0],[0,-70],[0,-70],[1,-1],[21,10],[42,90],[-42,-230]]
思路：一条直线有斜率和截距确定。所以以一个点为固定点，结合斜率就可以判断是否是同一条直线。
因为如果(A,B)，(A,C)不在一条直线上，那么固定B时,(B,C)一定不会与A共线。所以，两两计算判断即可。
因为斜率换成double类型可能因为精度问题导致hashmap有问题，所以若K = X /Y，则用 X与Y联合表示斜率。
每插入一条斜率，就记录椅子当前最大值，最后和全局最大值比较。
由于有重复的点，把重复点也要记录上。由于一条直线是由最少两个点组成，所以最后别忘把结果+1。
public class Solution{
public int maxPoints(Point[] points) {
if(points.length==0) return 0;
if(points.length==1) return 1;
if(points.length==2) return 2;
int res = 0;
HashMap<Integer,HashMap<Integer,Integer>> slope = new HashMap<Integer,HashMap<Integer,Integer>>();//slope,count
for(int i = 0;i < points.length ; i++){//anchor
slope.clear();
Point anchor = points[i];
int same = 0;
int max = 0;
for(int j = i+1;j < points.length; j++){
Point cur = points[j];
if(cur.x==anchor.x&&cur.y==anchor.y) {
same++;
continue;
}
//直接存斜率可能会因为double产生精度问题，导致hashmap统计出错
//所以要分别存储斜率K的分子与分母。并且要避免 1,2 与 2,4不相同的情况
//Double k = ((cur.x - anchor.x)==0)?Double.MAX_VALUE:((cur.y - anchor.y+0.0)/(cur.x - anchor.x));
int x = cur.x - anchor.x;
int y = cur.y - anchor.y;
int gcd=generateGCD(x,y);
if (gcd!=0){
x/=gcd;
y/=gcd;
}
if(slope.get(x)==null){
HashMap<Integer,Integer> subslope = new HashMap<Integer,Integer>();
subslope.put(y, 1);
slope.put(x,subslope);
}else{
if (slope.get(x).containsKey(y)){
slope.get(x).put(y, slope.get(x).get(y)+1);
}else{
slope.get(x).put(y, 1);
}
}
//System.out.println(cur.toString()+" K is:" + k);
max = Math.max(max, slope.get(x).get(y));
}
//System.out.println(slope);
//System.out.println("same:"+same);
res = Math.max(res, max+same+1);
}
return res ;
}
private int generateGCD(int a,int b){
if (b==0) return a;
else return generateGCD(b,a%b);
}
}