LeetCode | 149. Max Points on a Line求多个点里面在一条直线上的点最多有多少个难题

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

感觉我的想法太复杂了，不过暂时也只想得到这个方法，

我的方法大概的原理是两点决定一条直线，首先遍历原点数组，将其中的相同的点复制到另外一个点数组里面去，这样另外一个点的数组就不会有重复的点，

然后根据两个点决定一条直线，遍历点数组里面的点，看那些点在同一条直线上面，统计直线上面点的数量，接下来已经在直线上面的点就不需要遍历了，只需要遍历那些没有确定在哪条直线上的点就行了。

当所有的点都遍历完毕之后，所有的直线也就确定了，点最多的一条直线也就能够直接得到

这里还需要注意的是如何判断三个点共线，这里不能使用浮点数相除，因为精度的原因会导致错误，也不能把int赋给float，因为当int比较大的时候，将int赋给float会导致误差，所以只能考虑其他的方法来判断三点是否共线

由于三点的坐标都是int，所以可以取其中的两个点，求其横坐标差和纵坐标差的最大公约数，然后除以最大公约数，将待比较的点的坐标除以这个结果，如果除以的结果相等，这三点就共线，如果不相等，这三个点就不共线，处理这一步的时候还需要注意坐标可能会为负数

坐标为0的时候也要特别处理

以后做题的时候要尽量避免将int转换成float，要尽量避免int相除，要尽量避免将int转换成float，要尽量避免if等于号里面出现float运算!

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
     bool checkOnLine(int xL, int yL, int tmpX, int tmpY)
{
	 int a, b,tmp;
	 if (yL == 0 && tmpY == 0) return true;
	 if (xL == 0 && tmpX == 0) return true;
	 if (yL != 0 && tmpY != 0&& xL != 0 && tmpX != 0)
	 {
		 a = xL, b = yL;
		 while (a%b != 0)
		 {
			 tmp = a%b;
			 a = b;
			 b = tmp;
		 }
		 b = abs(b);
		 a = xL / b;
		 b = yL / b;
		 if (tmpX%a == 0 && tmpY%b == 0 && tmpX / a == tmpY / b)
			 return true;
	 }
	 return false;
}
 int getThePointN(int one,int two, vector<Point>& points, vector<vector<int>> & thePointMark, vector<int> &pointsSameCount)
{
	 int xL, yL,tmpX,tmpY;
	 int pCount = pointsSameCount[one]+ pointsSameCount[two];
	 vector<int> thePointW;
	 thePointW.push_back(one);	 thePointW.push_back(two);
	 xL = points[one].x - points[two].x;
	 yL = points[one].y - points[two].y;
	 for (int i = 0; i < points.size(); i++)
	 {
		 if (i != one&&i != two)
		 {
			 tmpX = points[i].x - points[one].x;
			 tmpY = points[i].y - points[one].y;
			 if (checkOnLine(xL,yL,tmpX,tmpY))
			 {
				 pCount+= pointsSameCount[i];
				 thePointW.push_back(i);
			 }
		 }
	 }
	 for (int i = 0; i<thePointW.size()-1; i++)
		 for (int j = i + 1; j <thePointW.size(); j++)
		 {
			 thePointMark[i][j] = pCount;
			 thePointMark[j][i] = pCount;
		 }
	 return pCount;
}
int maxPoints(vector<Point>& points) {
	int n = points.size();
	vector<Point> pointsNoSame;
	vector<bool> checkTheSame(n, false);
	vector<int> pointsSameCount;
	for (int i = 0; i < n; i++)
	{
		if (!checkTheSame[i])
		{
			int tmp = 1;
			for (int j = i + 1; j < n; j++)
			{
				if (points[i].x == points[j].x&&points[i].y == points[j].y)
				{
					checkTheSame[j] = true;
					tmp++;
				}

			}
			pointsNoSame.push_back(points[i]);
			pointsSameCount.push_back(tmp);
		}
	}
	n = pointsNoSame.size();
	if (n == 0) return 0;
	if (n == 1) return pointsSameCount[0];
	vector<vector<int>> thePointMark(n, vector<int>(n, -1));
	int theMaxN = 0;
	for(int i=0;i<n-1;i++)
		for (int j = i + 1; j < n; j++)
		{
			if (thePointMark[i][j] == -1)
			{
				theMaxN = max(getThePointN(i,j, pointsNoSame,thePointMark, pointsSameCount), theMaxN);
			}
		}
	return theMaxN;
}
};