当前位置：首页 > article >正文

c++ 计算同一行上的最大点数（Count maximum points on same line）

article 2024/10/9 13:57:41

示例图

给定二维平面上的 N 点作为一对 (x, y) 坐标，我们需要找到位于同一条线上的最大点数。

例子：

输入：points[] = {-1, 1}, {0, 0}, {1, 1},
{2, 2}, {3, 3}, {3, 4}

输出：4

那么位于同一条线上的点的最大数量为 4，这些点分别是 {0, 0}, {1, 1}, {2, 2}, {3, 3}

我们可以通过以下方法解决上述问题 - 对于每个点 p，计算其与其他点的斜率，并使用地图记录有多少个点具有相同的斜率，通过这种方式我们可以找出有多少个点与 p 在同一条线上。对于每个点继续执行相同的操作并更新迄今为止找到的最大点数。

实施过程中需要注意以下几点：

1、如果两个点是 (x1, y1) 和 (x2, y2)，则它们的斜率将是 (y2 – y1) / (x2 – x1)，这可能是一个双精度值，并且可能导致精度问题。为了消除精度问题，我们将斜率视为对 ((y2 – y1), (x2 – x1)) 而不是比率，并在插入到映射之前通过它们的 gcd 减少对。在下面的代码点中，垂直或重复的点被单独处理。

2、如果我们使用c++ 中的 unordered_map或Java 中的 HashMap来存储斜率对，则解决方案的总时间复杂度将为 O(n^2)，空间复杂度将为 O(n)。

示例代码：

/* C/C++ program to find maximum number of point
which lie on same line */
#include <bits/stdc++.h>
#include <boost/functional/hash.hpp>

using namespace std;

// method to find maximum collinear point
int maxPointOnSameLine(vector< pair<int, int> > points)
{
int N = points.size();
if (N < 2)
return N;

int maxPoint = 0;
int curMax, overlapPoints, verticalPoints;

// here since we are using unordered_map
// which is based on hash function
//But by default we don't have hash function for pairs
//so we'll use hash function defined in Boost library
unordered_map<pair<int, int>, int,boost::
hash<pair<int, int> > > slopeMap;

// looping for each point
for (int i = 0; i < N; i++)
{
curMax = overlapPoints = verticalPoints = 0;

// looping from i + 1 to ignore same pair again
for (int j = i + 1; j < N; j++)
{
// If both point are equal then just
// increase overlapPoint count
if (points[i] == points[j])
overlapPoints++;

// If x co-ordinate is same, then both
// point are vertical to each other
else if (points[i].first == points[j].first)
verticalPoints++;

else
{
int yDif = points[j].second - points[i].second;
int xDif = points[j].first - points[i].first;
int g = __gcd(xDif, yDif);

// reducing the difference by their gcd
yDif /= g;
xDif /= g;

// increasing the frequency of current slope
// in map
slopeMap[make_pair(yDif, xDif)]++;
curMax = max(curMax, slopeMap[make_pair(yDif, xDif)]);
}

curMax = max(curMax, verticalPoints);
}

// updating global maximum by current point's maximum
maxPoint = max(maxPoint, curMax + overlapPoints + 1);

// printf("maximum collinear point
// which contains current point
// are : %d\n", curMax + overlapPoints + 1);
slopeMap.clear();
}

return maxPoint;
}

// Driver code
int main()
{
const int N = 6;
int arr[N][2] = {{-1, 1}, {0, 0}, {1, 1}, {2, 2},
{3, 3}, {3, 4}};

vector< pair<int, int> > points;
for (int i = 0; i < N; i++)
points.push_back(make_pair(arr[i][0], arr[i][1]));

cout << maxPointOnSameLine(points) << endl;

return 0;
}