Given N point on a 2D plane as pair of (x, y) co-ordinates, we need to find maximum number of point which lie on the same line.
Examples:
Input : points[] = {-1, 1}, {0, 0}, {1, 1},
{2, 2}, {3, 3}, {3, 4}
Output : 4
Then maximum number of point which lie on same
line are 4, those point are {0, 0}, {1, 1}, {2, 2},
{3, 3}
We can solve above problem by following approach – For each point p, calculate its slope with other points and use a map to record how many points have same slope, by which we can find out how many points are on same line with p as their one point. For each point keep doing the same thing and update the maximum number of point count found so far.
Some things to note in implementation are:
1) if two point are (x1, y1) and (x2, y2) then their slope will be (y2 – y1) / (x2 – x1) which can be a double value and can cause precision problems. To get rid of the precision problems, we treat slope as pair ((y2 – y1), (x2 – x1)) instead of ratio and reduce pair by their gcd before inserting into map. In below code points which are vertical or repeated are treated separately.
2) If we use unordered_map in c++ or HashMap in Java for storing the slope pair, then total time complexity of solution will be O(n^2)
/* 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 colinear 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 colinear point // which contains current point // are : %d
", 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; } |
Output:
4
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
This article is attributed to GeeksforGeeks.org
leave a comment
0 Comments