Max Points on a Line.cpp

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
struct Fraction
{
    long sign, above, below;
    
    Fraction(long numerator, long denominator)
    {
        sign = (numerator < 0) ^ (denominator < 0)? -1: 1;
        above = abs(numerator);
        below = abs(denominator);
    }
};

bool operator==(const Fraction& f1, const Fraction& f2)
{
    return f1.sign == f2.sign && f1.above == f2.above && f1.below == f2.below;
}

struct hashFraction
{
    size_t operator()(const Fraction& f) const
    {
        string sign = f.sign == 1? "": "-";
        string str = sign + to_string(f.above) + "/" + to_string(f.below);
        return std::hash<string>{}(str);
    }
};

class Solution {
public:
    int maxPoints(vector<Point>& points) {
        int len = points.size(), res = 0;
        for(int i = 0; i < len; ++i)
        {
            unordered_map<Fraction, int, hashFraction> map;
            int dup = 1, currMax = 0;
            for(int j = 0; j < len; ++j)
            {
                if(j == i)continue;
                long y = (long)points[j].y - (long)points[i].y, x = (long)points[j].x - (long)points[i].x;
                if(!x && !y)
                    ++dup;
                else
                {
                    long div = gcd(y, x);
                    Fraction f(y / div, x / div);
                    ++map[f];
                    currMax = max(currMax, map[f]);
                }
            }
            res = max(res, currMax + dup);
        }
        return res;
    }
    
private:
    long gcd(long a, long b)
    {
        a = abs(a);
        b = abs(b);
        if(a < b)return gcd(b, a);
        if(!b)return a;
        return gcd(b, a % b);
    }
};