Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
给定2D平面上的n个点，找到位于同一直线上的最大点的数量。
首先明确如何量化"直线"这一概念，最简单的，我们可以固定一个起始点S（Start），然后遍历剩余的所有点，记做E（End），如果有两个E（记做E1和E2），满足$(E1.x-S.x)/(E1.y-S.y)=(E2.x-S.x)/(E2.y-S.y)$,那么就可以确定E2在S与E1确定的直线上，而$(E1.x-S.x)/(E1.y-S.y)$刚好表示的是以E1和S构成的直线的斜率。所以我们就可以得出结论：要确定三个点S、E1、E2是否在同一条直线上即E2在S、E1构成的唯一直线上，只要满足S-E1直线的斜率与S-E2直线的斜率相等即可。
明确了如何判断三个点是否在一条直线之后我们再回过头来看这道题，n个点，找出点数最多的直线上的点的数量。注意，题目中没有说n个点两两都不相同，所以可能出现多个点的x、y相等，这时候应该多计算一个点(重复的点也是点)。我们可以使用两个循环，第一个循环从第一个点开始遍历所有点作为起始点S，第二个循环从起始点的下一个点遍历后面所有的点作为重点E，构建Map存储当前S对应的所有斜率下的最大点值，逻辑如下：
maxCount=0;
for indexS from 0 to Length:
Map<斜率，点数量> map
//以indexS对应点为起点的所有直线中点数量的最大值
tempMaxCount=1
//与当前indexS对应点重合的点的数量
commonCount=0
for indexE from indexS+1 to Length:
if point[indexS]==point[indexE]:
//如果两个点重合
commonCount+=1
else :
斜率=求斜率的函数(point[indexS],point[indexE])
//如果当前斜率之前已经被加入Map中，则更新最大点数为原来的点数+1
if(map.containsKey(斜率)){
tempMaxCount=max(tempMaxCount,map.get(斜率)+1)
map.put(斜率，map.get(斜率)+1)
}else{
tempMaxCount=2
map.put(斜率，2)
}
maxCount=max(maxCount,tempMaxCount+commonCount)
return maxCount
以上就是完整的逻辑，有几个细节需要注意：
-
斜率的精度
不管使用float还是double都会涉及斜率精度取舍的问题，所以这里建议使用字符串保存精度，方法是将两个点x距离和y距离的比值化为最简分数，然后转化为字符串表示
-
x距离或y距离为0
由于存在两个点在同一条横线或同一条竖线的可能，这是如果还是和化普通分数那样就不可取，比如0/4和0/9化为字符串后不一样，但是其表示的值是一样的，所以这种情况应该单独考虑
完整逻辑请看详细代码。
public int maxPoints(Point[] points) {
int length = points.length;
int maxPointCount = 0;
for (int startIndex = 0; startIndex < length; startIndex++) {
Map<String, Integer> maxPointMap = new HashMap<>();
int commonPointCount = 0;
int tempMaxCount = 1;
for (int endIndex = startIndex + 1; endIndex < length; endIndex++) {
int distanceX = points[startIndex].x - points[endIndex].x;
int distanceY = points[startIndex].y - points[endIndex].y;
if (distanceX == 0 && distanceY == 0) {
commonPointCount += 1;
} else {
String curStrDis;
if (distanceX == 0) {
curStrDis = "distanceX";
} else if (distanceY == 0) {
curStrDis = "distanceY";
} else {
int maxCommonDivisor = commonDivisor(distanceX, distanceY);
if (maxCommonDivisor != 0) {
distanceX = distanceX / maxCommonDivisor;
distanceY = distanceY / maxCommonDivisor;
}
int flag = 0;
if (distanceX < 0) {
distanceX = -distanceX;
flag++;
}
if (distanceY < 0) {
distanceY = -distanceY;
flag++;
}
curStrDis = String.valueOf(distanceX) + distanceY;
if (flag == 1) {
curStrDis = "-" + curStrDis;
}
}
if (maxPointMap.containsKey(curStrDis)) {
tempMaxCount = Math.max(tempMaxCount, maxPointMap.get(curStrDis) + 1);
maxPointMap.put(curStrDis, maxPointMap.get(curStrDis) + 1);
} else {
//初始时put进去2，一个点是起始点，另一个点是当前点
maxPointMap.put(curStrDis, 2);
tempMaxCount = Math.max(tempMaxCount, 2);
}
}
}
maxPointCount = Math.max(maxPointCount, tempMaxCount + commonPointCount);
}
return maxPointCount;
}