[LeetCode] 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.

Analysis:

Get lines passing every two, and compare.

If we get all of them n*(n-1)/2, then we still need compare them all. that will be O(n^4).

By using map, and round function, we need to check just the lines with the same property.

But to store a line, at least two property are needed, either two points, or slope and intersect. And compare them is still boring and time consuming. we could use nested map, but we try to avoid that.

what about calculating all line passing by the same point, store those lines' slope in map and check for only once.O(n) for each node. And O(n^2) totally. Not a bad idea. Let's try it.



(I adjust the epsi (i.e. epsilon several times), and 1.0e-5 passed the test cases. It's just weird that 1.0e-3, 1.0e-4, 1.0e-6, 1.0e-7 cannot pass the test, and only 1.0e-5 does.... -_-. Life is like this. But still, something wonderful is ahead!)

 #include <unordered_map>  
 #include <vector>  
  //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:  
   Solution():epsi(1.0e-5){}  
   int maxPoints(std::vector<Point> &points)  
   {  
     if(points.size()==0)  
       return 0;  
     int max = 0;  
     int n = points.size();  
     std::unordered_map<double, int> map;  
     for(int i=0; i<n; i++)  
     {  
       map.clear();  
       int samePoints=0;  
       for(int j=0; j<n; j++)  
       {  
         if(points[i].x == points[j].x && points[i].y == points[j].y){  
           samePoints++;  
           continue;  
         }  
         double k;   
         if(points[i].x == points[j].x)  
           k = INT_MAX;  
         else  
           k = 1.0*(points[i].y - points[j].y)/(points[i].x - points[j].x); // must add 1.0* at first  
         k = getRound(k);  
         if(map.find(k)==map.end())  
           map[k]=1;  
         else  
           map[k]++;  
       }  
       std::unordered_map<double, int>::iterator iter;  
       int tmp=0;  
       for(iter=map.begin(); iter!=map.end(); iter++)  
         tmp = iter->second > tmp ? iter->second : tmp;  
       tmp += samePoints;  
       max = max > tmp ? max : tmp;  
     }  
     return max;  
   }  
   double getRound(double d)  
   {  
     int val = floor(d/epsi);  
     return val * epsi;  
   }  
   bool compare(double d1, double d2)  
   {  
     if(d1-d2<epsi && d2-d1<epsi)  
       return true;  
     else  
       return false;  
   }  
 private:  
   double epsi;  
 };