Max Points on a Line Solutions in C++

// Source : https://oj.leetcode.com/problems/max-points-on-a-line/
// Author : Hao Chen
// Date   : 2014-10-12



#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Point {
    int x;
    int y;
    Point() : x(0), y(0) {}
    Point(int a, int b) : x(a), y(b) {}
};

// O(n^2) time complexity solution
int maxPoints(vector<Point> &points) {

    #define INT_MAX 2147483647
    #define INT_MIN (-INT_MAX - 1)

    if (points.size()<=0) return 0;
    if (points.size()<=2) return points.size();
    
    int maxnum = 0;
    //using a map to find the same slope line
    map<double, int> slopeMap;

    //The algorithm here is quite straight forward.
    //   take each point in array to caculate with others
    //
    //Actually the algorithm here can be optimized.
    //   there are many duplicated calculation. 
    //   considering two points A and B, (A,B) is same with (B,A), here re-calculated.
    for(int i=0; i<points.size(); i++) {
        //reset teh slope map.
        slopeMap.clear();
        slopeMap[INT_MIN] = 0;
        int samePointCnt = 1;
        for (int j=0; j<points.size(); j++) {
            if (i==j) continue; //skip the same point
            //Caculate the slope of two points
            int delta_x = points[i].x - points[j].x;
            int delta_y = points[i].y - points[j].y;
            //Special case: two points are exactly at same place
            if (delta_y == 0 && delta_x == 0){
                samePointCnt++;
                continue;
            }
            //Special case: delta_x == 0
            double slope = INT_MAX;
            if (delta_x!=0) {
                slope = 1.0*delta_y / delta_x;
            }
            //Count the points is same line.
            slopeMap[slope]++;
        }
        //find the max number of points located at same line with points[i]
        map<double, int>::iterator it;
        for (it = slopeMap.begin(); it != slopeMap.end(); it++) {
            if (maxnum < it->second + samePointCnt) {
                maxnum = it->second + samePointCnt;
            }
        }
    }

    return maxnum;
}

void generatePoints(vector<Point> &points, int n) {
    srand(time(0));
    Point p;
    for(int i=0; i<n; i++) {
        p.x = rand() % 1;
        p.y = rand() % 1;
        points.push_back(p);
    }
}

void printPoints(vector<Point> &points) {
    for(int i=0; i<points.size(); i++) {
        cout << "(" << points[i].x << "," << points[i].y << ") ";
    }
    cout << endl;
}


int main(int argc, char** argv) 
{
    int n = 20;
    if ( argc > 1) {
        n = atoi(argv[1]);
    }
    vector<Point> points;
    generatePoints(points, n);
    printPoints(points);
    cout << maxPoints(points) << endl;
    return 0;
}

/// Source : https://leetcode.com/problems/max-points-on-a-line/
/// Author : liuyubobobo
/// Time   : 2017-07-17

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


/// Definition for a point.
struct Point {
    int x;
    int y;
    Point() : x(0), y(0) {}
    Point(int a, int b) : x(a), y(b) {}
};


/// Using Hash Map
/// Using string to record the slopes
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {
public:
    int maxPoints(vector<Point>& points) {

        if( points.size() <= 1 )
            return points.size();

        int res = 1;
        for( int i = 0 ; i < points.size() ; i ++ ){

            unordered_map<string, int> record;
            int samePoint = 0;
            for( int j = 0 ; j < points.size() ; j ++ ){

                if( points[i].x == points[j].x && points[i].y == points[j].y )
                    samePoint ++;
                else
                    record[getPairStr(slope(points[j], points[i]))]++;
            }

            res = max(res, samePoint);    // In case the record is empty and all the points are in the same point.
            for( unordered_map<string,int>::iterator iter = record.begin() ; iter != record.end() ; iter ++ )
                res = max( res , iter->second + samePoint );
        }

        return res;
    }

private:
    pair<int,int> slope( const Point &pa, const Point &pb ){

        int dy = pa.y - pb.y;
        int dx = pa.x - pb.x;
        if( dx == 0 )
            return make_pair(1,0);
        if( dy == 0 )
            return make_pair(0,1);

        int g = gcd( abs(dy), abs(dx) );
        dy /= g;
        dx /= g;
        if( dx < 0 ){
            dy = -dy;
            dx = -dx;
        }
        return make_pair( dy , dx );
    }

    int gcd( int a , int b ){

        if( a < b )
            swap( a , b );

        if( a % b == 0 )
            return b;

        return gcd( b , a%b );
    }

    string getPairStr( const pair<int,int> p){
        return to_string(p.first) + "/" + to_string(p.second);
    }
};

int main() {

    vector<Point> pvec1;
    pvec1.push_back( Point(1, 1) );
    pvec1.push_back( Point(1, 1) );
    //pvec1.push_back( Point(2, 3) );
    //pvec1.push_back( Point(3, 3) );

    cout<<Solution().maxPoints(pvec1)<<endl;

    return 0;
}

/// Source : https://leetcode.com/problems/max-points-on-a-line/
/// Author : liuyubobobo
/// Time   : 2017-07-17

#include <iostream>
#include <vector>
#include <map>

using namespace std;


/// Definition for a point.
struct Point {
    int x;
    int y;
    Point() : x(0), y(0) {}
    Point(int a, int b) : x(a), y(b) {}
};

/// Using Hash Map
/// Using pair directly to record the slopes
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {
public:
    int maxPoints(vector<Point>& points) {

        if( points.size() <= 1 )
            return points.size();

        int res = 1;
        for( int i = 0 ; i < points.size() ; i ++ ){

            map<pair<int,int>, int> record;
            int samePoint = 0;
            for( int j = 0 ; j < points.size() ; j ++ ){

                if( points[i].x == points[j].x && points[i].y == points[j].y )
                    samePoint ++;
                else
                    record[slope(points[j], points[i])]++;
            }

            res = max(res, samePoint);    // In case the record is empty and all the points are in the same point.
            for( map<pair<int,int>,int>::iterator iter = record.begin() ; iter != record.end() ; iter ++ )
                res = max( res , iter->second + samePoint );
        }

        return res;
    }

private:
    pair<int,int> slope( const Point &pa, const Point &pb ){

        int dy = pa.y - pb.y;
        int dx = pa.x - pb.x;
        if( dx == 0 )
            return make_pair(1,0);
        if( dy == 0 )
            return make_pair(0,1);

        int g = gcd( abs(dy), abs(dx) );
        dy /= g;
        dx /= g;
        if( dx < 0 ){
            dy = -dy;
            dx = -dx;
        }
        return make_pair( dy , dx );
    }

    int gcd( int a , int b ){

        if( a < b )
            swap( a , b );

        if( a % b == 0 )
            return b;

        return gcd( b , a%b );
    }
};

int main() {

    vector<Point> pvec1;
    pvec1.push_back( Point(1, 1) );
    pvec1.push_back( Point(1, 1) );
    //pvec1.push_back( Point(2, 3) );
    //pvec1.push_back( Point(3, 3) );

    cout<<Solution().maxPoints(pvec1)<<endl;

    return 0;
}