欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

位于同一直线上的点(2D/3D)

程序员文章站 2022-03-02 10:56:00
...

题目一:给定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;
	}
}