Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
思路：
两次循环求每个点和其他点连线的斜率，斜率相同则在一条直线，最后统计斜率相同的最多的个数。
用斜率由于小数精度问题，有一些case会有bug，因此把斜率转化为分数形式，分子分母组成key。
public int maxPoints(Point[] points) {
if (points == null) {
return 0;
}
if (points.length <= 2) {
return points.length;
}
int res = 0;
for (int i = 0; i < points.length; i++) {
HashMap<String, Integer> map = new HashMap<>();
int cnt = 0, duplicate = 0;
for (int j = i + 1; j < points.length; j++) {
int diffy = points[j].y - points[i].y;
int diffx = points[j].x - points[i].x;
if (diffx == 0 && diffy == 0) {
duplicate++;
continue;
}
int gcd = getGCD(diffx, diffy);
if (gcd!=0){
diffx /= gcd;
diffy /= gcd;
}
String key = String.valueOf(diffx) + "_" + String.valueOf(diffy);
map.put(key, map.getOrDefault(key, 0) + 1);
cnt = Math.max(cnt, map.get(key));
}
res = Math.max(res, duplicate + cnt + 1);
}
return res;
}
private int getGCD(int diffx, int diffy) {
if (diffy == 0) {
return diffx;
}
return getGCD(diffy, diffx % diffy);
}