Count maximum points on same line in C++

In this tutorial, we are going to program on how to Count maximum points on the same line in C++. Firstly we will have an Introduction on points in 2-D planes and slope. Secondly, demonstrate the solution with c++ code.

Introduction

In a 2-D plane, a point can be shown using two points. Example (x,y). This shows a point in the 2-D plane. The first coordinate “x” shows distance from the origin in the horizontal direction. Second coordinate “y” shows distance from the origin in the vertical direction.

Line in a 2-D plane is denoted using two points and a slope. A line can extend in both directions.

If we have to find if the point lies on the line it has to have the same slope. In this problem, we have to find the number of coordinates which all lie on the same line.

To solve this problem we will be using the hash table, unordered map and vectors.

Algorithm to solve this problem:

Algorithm that will be used to solve this problem is :

  1. To know if the two points are on the same line we have to calculate the slope using two points. Then keep on comparing with other pair combinations.
  2. Once we have found a pair then store it in unordered_map.

Program in C++ to count maximum points on the same line

#include <bits/stdc++.h> 
#include <boost/functional/hash.hpp> 
  
using namespace std;  
int maxPointOnSameLine(vector< pair<int, int> > points) 
{ 
    int n = points.size(); 
    if (n < 2) 
        return n; 
  
    int maxPoint = 0; 
    int curMax, overlapPoints, verticalPoints; 
    
    unordered_map<pair<int, int>, int,boost:: 
              hash<pair<int, int> > > slopeMap; 

    for (int i=0;i<n;i++) 
    { 
        curMax = overlapPoints = verticalPoints = 0; 
 
        for (int j=i+1; j<n; j++) 
        { 

            if (points[i] == points[j]) 
                overlapPoints++; 

            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); 
  
                yDif /= g; 
                xDif /= g; 

                slopeMap[make_pair(yDif, xDif)]++; 
                curMax = max(curMax, slopeMap[make_pair(yDif, xDif)]); 
            } 
  
            curMax = max(curMax, verticalPoints); 
        } 

        maxPoint = max(maxPoint, curMax + overlapPoints + 1); 

        slopeMap.clear(); 
    } 
  
    return maxPoint; 
} 

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; 
}

Input and Output:

Enter the number of coordinates : 6
Enter the coordinates : -1 1
0 0
1 1
2 2
3 3
3 4
Points that are at same line are : 4

Conclusion

This tutorial on Count maximum points on the same line in C++ contains many important concepts. Firstly the concept of the 2-D plane in c++. Secondly the use of unordered_map and finally on how to use slope to create a relation between points.

Also Checkout :

How to change case of a character using bit manipulation in C++

Leave a Reply

Your email address will not be published. Required fields are marked *