[Rainbow] thanks to the post from @jianchao.li.fighter


  • 0
    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            unordered_map<double, int> slopes;
            int result=0, n=points.size();
            for(int i=0; i<n; i++){
                slopes.clear();
                int duplicate=1;
                for(int j=i+1; j<n; j++){
                    if(points[j].x==points[i].x && points[j].y==points[i].y){
                        duplicate++;
                        continue;
                    }
                    double slope = (points[j].x==points[i].x) ? INT_MAX : 
                        (double)(points[j].y-points[i].y)/(points[j].x-points[i].x);
                    slopes[slope]++;
                }
                result=max(result, duplicate);
                for(auto slope : slopes)  result=max(result, slope.second+duplicate);
            }
            return result;
        }
    };

  • 0
    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            map<pair<int, int>, int> slopes;
            int result=0, n=points.size();
            for(int i=0; i<n; i++){
                slopes.clear();
                int duplicate=1;
                for(int j=i+1; j<n; j++){
                    if(points[i].x==points[j].x && points[i].y==points[j].y){
                        duplicate++;
                        continue;
                    }
                    int dx=points[j].x-points[i].x;
                    int dy=points[j].y-points[i].y;
                    int dvs=gcd(dx, dy);
                    slopes[make_pair(dx/dvs, dy/dvs)]++;
                }
                
                result=max(result, duplicate);
                for(auto slope:slopes){
                    result=max(result, slope.second+duplicate);
                }
            }
            
            return result;
        }
        
        int gcd(int num1, int num2){
            while(num2){
                int temp=num2;
                num2=num1%num2;
                num1=temp;
            }
            return num1;
        }
    };

Log in to reply
 

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