O(n^2) C++ solution using atan2l and unordered_map


  • 2
    B

    The dod variable is handling duplicate points. ny, nx - new y, new x

    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            int ans=0,ny,nx,dod;
            if (points.size()==1) {
                return 1;
            }
            long double t;
            unordered_map<long double,int> h;
            for (int i=0; i<points.size(); i++) {
                dod=0;
                for (int j=0; j<points.size(); j++) {
                    if (i!=j) {
                        ny=points[j].y-points[i].y;
                        nx=points[j].x-points[i].x;
                        if (ny==0 && nx==0) {
                            dod++;
                            ans=max(ans,dod+1);
                        }
                        else {
                            t=atan2l(ny,nx);
                            if (t<0) {
                                t+=M_PI;
                            }
                            h[t]++;
                            ans=max(ans,h[t]+dod+1);
                        }
                    }
                }
                h.clear();
            }
            return ans;
        }
    };
    

Log in to reply
 

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