首页 > 代码库 > Max Points on a Line

Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

/** * 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) {        if(points.size() <= 2) //size is less then or equal to 2 then just return size        return points.size();        unordered_map<string, int> dupMap;        for(int i = 0; i < points.size(); i++){ // delete dubs and keep track of their count in dupMap            string pt = to_string(points[i].x) +  + to_string(points[i].y);            if(dupMap.count(pt) == 0)                dupMap[pt] = 0;            else{                dupMap[pt]++;                points.erase(points.begin() + i--);            }        }                if(points.size() == 1){ //if every item  was a dup            string pt = to_string(points[0].x) +  + to_string(points[0].y);            return dupMap[pt] + 1;        }            int max = 2;        for(int i = 0; i < points.size()-1; i++){//O(N^2) calclate every combination of points            unordered_map<string, int> hashMap;            string pt = to_string(points[i].x) + + to_string(points[i].y);                for(int j = i+1; j < points.size(); j++){                string pt2 = to_string(points[j].x) + + to_string(points[j].y);                string eq = "";                if(points[i].x == points[j].x)                    eq = "x = " + to_string(points[i].x); //infinte slope                else{                    float m = (float)(points[j].y - points[i].y) / (float)(points[j].x - points[i].x);//slope                    m = (m < 0.0005 && m > -0.0005)? 0: m; //rounding to 0 for floats                    float b = (float)points[i].y - (float)(m * points[i].x);                    eq = "y =" + to_string(m) + + + to_string(b); //form equation string                }                    if(hashMap.count(eq) == 0){ //havent seen this eq before                    hashMap[eq] = 2;                    if(dupMap[pt] > 0) //pt has dupes                        hashMap[eq] += dupMap[pt];                    if(dupMap[pt2] > 0)//pt2 has dupes                        hashMap[eq] += dupMap[pt2];                }                else                    hashMap[eq] += (dupMap[pt2] > 0)? dupMap[pt2] + 1 : 1;                max = (hashMap[eq] > max)? hashMap[eq] : max;            }        }        return max; //return the max count    }};

 

Max Points on a Line