位于同一直线上的点（2D/3D）

题目一：给定N个二维坐标点(包含整形x,y)，找到位于同一条直线上点的最大个数。 

题目二：给定N个三维坐标点(包含整形x,y,z)，找到位于同一条直线上点的最大个数 。

思路：双循环O(N^2)。 先找第一个点 i ，把它固定住，计算出剩余所有点 j 与它的连线斜率，凡是斜率相同的都是共线的点。统计所有出现过的斜率，次数最高的斜率也对应了“穿过点 i 并且共线点最多的那条线” 。 然后再找下一个点 i+1 ，固定住，求出穿过 i+1并且共线点最多的那条线。依次遍历。

斜率可以直接用dy/dx计算出的浮点数表示，也可以用pair(dx,dy)表示。分别对应 map<float, int> 和 map<pair<int,int>,int>. 前者的缺点是浮点数的精度问题，在计算机中浮点数相等不能简单的用==号，而且竖线的斜率是无穷大的，无法表示。所以用后者更简洁安全，需要化简成最简形式(同除以最大公约数gcd)，否则会出现同一个斜率却有多个不同的(dx,dy)的情况。这个化简对横线和竖线也同样有效，因为gcd(n,0)=gcd(0,n)=n, 所以对于dx和dy中有一个为零的情况，同除以gcd后会变成(1,0)或(0,1).

需要注意的是坐标点可能存在重合的情况，与基准点重合的点是可以算进任何斜率里的，所以需要单独考虑。

问题一的代码：

#include<vector>
#include<map>
#include<iostream>
using namespace std;
struct Point {
	int x;
	int y;
	Point() : x(0), y(0) {}
	Point(int a, int b) : x(a), y(b) {}
};
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int max(int a, int b) { return a > b ? a : b; }
int maxPoints(vector<Point>& points) {
	int ans = 0;
	for (int i = 0; i < points.size(); i++) {
		int cnt = 0,overLap=0;
		map<pair<int, int>, int> line;
		for (int j = i + 1; j < points.size(); j++) {//i之前的点没必要再遍历
			int dx = points[i].x - points[j].x;
			int dy = points[i].y - points[j].y;
			//判断两点是否重合
			if (dx == 0 && dy == 0) {
				++overLap;
				continue;
			}
			//计算最简方向向量并存入map容器中,同时更新cnt
			int g = gcd(dx, dy);
			dx /= g;
			dy /= g;
			cnt=max(cnt,++line[pair<int, int>(dx, dy)]);
		}
		//统计该基准点下的最大共线点数量
		//cnt+重合点+基准点自身
		ans = max(ans, cnt + overLap + 1);
	}
	return ans;
}

参考链接：https://blog.csdn.net/sinat_35261315/article/details/79255553

3D的情况是类似的，唯一不同是多个维度，所以斜率(准确得说是方向向量)用(dx,dy,dz)表示，代码如下, 但只能通过90%的案例，提示运行错误:请检查是否存在数组、列表等越界非法访问，内存非法访问等情况，terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc.

OJ原题：https://www.nowcoder.com/questionTerminal/7f1490a737024704a3f2b7aad476e3ac

#include<vector>
#include<map>
#include<iostream>
using namespace std;
struct Point {
	int x;
	int y;
	int z;
	Point() : x(0), y(0),z(0) {}
	Point(int a, int b,int c) : x(a), y(b),z(c) {}
};
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); }
int max(int a, int b) { return a > b ? a : b; }
int maxPoints(vector<Point>& points) {
	int ans = 0;
	for (int i = 0; i < points.size(); i++) {
		int cnt = 0,overLap=0;
		map<pair<pair<int, int>, int>,int> line;
		for (int j = i + 1; j < points.size(); j++) {
			int dx = points[i].x - points[j].x;
			int dy = points[i].y - points[j].y;
			int dz = points[i].z - points[j].z;
			//判断两点是否重合
			if (dx == 0 && dy == 0&&dz==0) {
				++overLap;
				continue;
			}
			//计算最简方向向量并存入map容器中,同时更新cnt
			int g = gcd(dx, dy,dz);
			dx /= g;
			dy /= g;
			dz /= g;
			cnt=max(cnt,++line[pair<pair<int, int>,int>(pair<int,int>(dx, dy),dz)]);			
		}
		//统计该基准点下的最大共线点数量
		//cnt+重合点+基准点自身
		ans = max(ans, cnt + overLap + 1);
	}
	return ans;
}
int main() {
	int n;
	int a, b;
	while (cin >> a>>b) {
		vector<Point> points(n);
		for (int i = 0; i < n; i++) 
			cin >> points[i].x >> points[i].y>>points[i].z;
		cout << maxPoints(points) << endl;
	}
}