Max Points on a Line

Solution 1:

 int maxPoints(vector<Point> &points){
            int n = points.size();
            if (n < 3) return n;
            int ret = 0;
            for (int i = 0; i < n; i++) {
                unordered_map<double, int> slopes;
                int dup = 1;
                int localMax = 0;
                for(int j = i+1; j < n; j++) {
                    if (points[i].x == points[j].x && points[i].y == points[j].y)
                        dup++;
                    else {
                       double x = points[i].x - points[j].x;
                       double y = points[i].y - points[j].y;
                       double slop = x == 0? numeric_limits<double>::max() : y/x;
                       localMax = max(localMax, ++slopes[slop]);
                    }
                }
                ret = max(ret, dup+localMax);
            }
             return ret;
        }

Solution 2:

  int maxPoints(vector<Point> &points){
            int n = points.size();
            if (n < 3) return n;
            int ret = 0;
            for (int i = 0; i < n; i++)
            {
                unordered_map<int, unordered_map<int, int>> slopes;
                int dup = 1;
                int localMax = 0;
                for(int j = i+1; j < n; j++)
                {
                    if (points[i].x == points[j].x && points[i].y == points[j].y)
                        dup++;
                    else
                    {
                       int x = points[i].x - points[j].x;
                       int y = points[i].y - points[j].y;
                       int gcd = GCD(x, y);
                       if (gcd != 0)
                       {
                           x /= gcd;
                           y /= gcd;
                       }
                       localMax = max(localMax, ++slopes[x][y]);
                    }
                }
                ret = max(ret, dup+localMax);
            }
             return ret;
        }
       
        int GCD(int a, int b)
        {
            if (b == 0) return a;
            return GCD(b, a%b);
        }

Solution 3:

 bool equals(float a, float b)
    {
       return abs(a-b) <= 1.0e-9;
    }
   
    int LongestPoints(vector<float> &slopes)
    {
        sort(slopes.begin(), slopes.end());
        int n = slopes.size();
        int counter = 1;
        int start = 0;
        int output = 0;
        for(int i =1; i < n; i++)
        {
            if (!equals(slopes[i], slopes[i-1]))
            {
                output = max(output,  i-start);
                start = i;
            }
        }
        output = max(output, n-start);
        return output;
    }
    int maxPoints(vector<Point> &points)
    {
        int n = points.size();
        if (n < 3) return n;
        int maxPts = 2;
       
        for (int i = 0; i < n; i++)
        {
            vector<float> slopes;
            int dup = 1;
            for(int j = i+1; j < n; j++)
            {
                float slope = numeric_limits<float>::max();
                if (points[i].x == points[j].x && points[i].y == points[j].y)
                    dup++;
                else {
                    if (points[i].x != points[j].x)
                       slope = (float)(points[i].y-points[j].y)/(float)(points[i].x-points[j].x);
                    slopes.push_back(slope);
                }
            }
           
            int longestPoints = LongestPoints(slopes);
            maxPts = max(maxPts, dup + longestPoints);
        }
       
        return maxPts;
    }