C++ solution (faster then average c++ submission)


  • -2
    4
    bool equalP(Point & a, Point & b)
    {
            return (a.x == b.x) && (a.y == b.y);
    }
    bool comparison( Point a, Point b)
    {
            if( a.x < b.x) return 1;
            if( a.x == b.x ) return (a.y < b.y);
            return 0;
    }
    class Solution {
            
            bool onLine(Point a, Point b, Point c)
            {
                    return (a.y - b.y) * (a.x - c.x) == (a.y - c.y) * (a.x - b.x);
            }
    public:
            int maxPoints(vector<Point> &points)
            {
                    sort( points.begin(), points.end(), comparison);
    
                    if( points.size() <= 2 ) return points.size();
                    
                    vector< pair< Point, int > > vp;
                    
                    Point temp = points[0];
                    int count2 = 1;
                    for( int i = 1; i < points.size(); ++i )
                    {
                            if( equalP(temp, points[i]) ) count2++;
                            else
                            {
                                    pair< Point, int > tp;
                                    tp.first = temp;
                                    tp.second = count2;
                                    vp.push_back(tp);
                                    temp = points[i];
                                    count2 = 1;
                            }
                    }
                    pair< Point, int > tp;
                    tp.first = points[points.size()-1];
                    tp.second = count2;
                    vp.push_back(tp);
                    
                    int max = 0;
                    for( int i = 0; i < vp.size(); ++i )
                    {
                            int count = vp[i].second;
                            if( count > max ) max = count;
                            for(int j = i + 1; j < vp.size(); ++j )
                            {
                                    count = vp[i].second + vp[j].second;
                                    for(int k = j + 1; k < vp.size(); ++k)
                                    {
                                            if( onLine(vp[i].first, vp[j].first, vp[k].first)) count += vp[k].second;
                                    }
                                    if( count > max ) max = count;
                            }
                    }
                    return max;
            }
    };

  • 0
    A

    I think it's O(n^3), but why it's so fast?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.