Answer to Question #209512 in C++ for Sandy

Question

Vertical Line that Passes through Maximum Number of Points Given 'n' points, design an algorithm and write a C++ code to find the end points of the vertical line that may be formed and that passess through maximum number of points. If there are more than one line that passess through maximum number of points then print the end points of the vertical line that passes through maximum number of points and of maximum length. For example, consider the ten points (3,5), (3, 10), (3, 15), (14, 15), (3, 85), (4, 11), (4, 15), (2, 2), (4, 70), (4,72), there are two vertical lines passing through four points and their end points are (3,5) - (3, 85) and (4,11) – (4, 72). Since both pass through same number of points, print the line with maximum length and it is (3,5) and (3, 85).

Answer 1

#include <map>
//Importing map library
#include <iostream>
//importing vector library
#include <vector>
//Imported for cout and cin functions
using namespace std;


int main()
{


    // total_points indicates the total points
    int total_points;


    cout << "Enter the total number of points: " ;


    cin >> total_points ;


    //This map contains the points with the same x coordinates


    map<int, int> Xfrequency;


    // The entered coordinates are stored in pairs' vector 


    vector<pair<int, int>> all_coordinates;


    // Enter cordinates of a given points


    for(int n=0; n<total_points; n++){


        int X_coordinates,Y_coordinates;


        cout<< "coordinate X" << n+1 << ": ";


        cin >> X_coordinates;


        cout<< "coordinate Y" << n+1 << ": ";


        cin >> Y_coordinates;


       


        Xfrequency[X_coordinates]++;


        // insert the point in vector of pair


        all_coordinates.push_back(make_pair(X_coordinates, Y_coordinates));


    }


    //Obtaining the total number of points that can lie on strainght line


    int highest_point_in_line= -1;


    for(pair<int, int> iterate: Xfrequency){


        if(iterate.second > highest_point_in_line){


            highest_point_in_line = iterate.second;


        }


    }


    //The below frequency is the same as the total possible points in a line


    for(pair<int, int> iterate: Xfrequency){


        if(iterate.second == highest_point_in_line){


            int maximum_Y = INT_MIN;


            int minimum_Y = INT_MAX;


            int temp_X = iterate.first;


            
            for(int i=0; i<all_coordinates.size(); i++){


                if(all_coordinates[i].first==temp_X){


                    if(all_coordinates[i].second > maximum_Y){


                        maximum_Y = all_coordinates[i].second;


                    }


                    if(all_coordinates[i].second < minimum_Y){


                        minimum_Y = all_coordinates[i].second;


                    }


                }


            }


       
              cout << "X and Y coordinate of the point : (" << temp_X <<","<<minimum_Y<<")"<< endl ;


             cout << "X and Y coordinate  of the point: (" << temp_X <<","<<maximum_Y<<")"<< endl ;
        }


        cout << endl  ;


    }


}