simple C++ n^2logn solution


  • 0
    N
    /**
     * Definition for a point.
     * struct Point {
     *     int x;
     *     int y;
     *     Point() : x(0), y(0) {}
     *     Point(int a, int b) : x(a), y(b) {}
     * };
     */
    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            int ret = min((int)points.size(), 1);
            map<pair<int, int>, int> hash;
            for (int i = 0; i < points.size(); ++ i){
                hash.clear();
                for (int j = 0; j < points.size(); ++ j)
                        hash[getPair(points[j].x - points[i].x, points[j].y - points[i].y)] ++;
                for (auto& p : hash)
                    ret = max(ret, p.second + (p.first == make_pair(0, 0) ? 0 : hash[make_pair(0, 0)]));
            }
            return ret;
        }
        
    private:
        pair<int, int> getPair(int x, int y){
            int tmp = GCD(abs(x), abs(y));
            x /= (tmp == 0 ? 1 : tmp);
            y /= (tmp == 0 ? 1 : tmp);
            return make_pair(x, y);
        }
        
        int GCD(int a, int b) {
            if (b == 0) return a;
            return GCD(b, a%b);
        }
    };
    

Log in to reply
 

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