1 #include <iostream> 2 #include <algorithm> 3 #include <unordered_map> 4 #include <vector> 5 #include <limits> 6  7 using namespace std; 8  9 /**10  * Definition for a point.11  * struct Point {12  *     int x;13  *     int y;14  *     Point() : x(0), y(0) {}15  *     Point(int a, int b) : x(a), y(b) {}16  * };17  */18  19 bool typeisless(const Point &data1,const Point &data2){20     return data1.x < data2.x;21 }22  23 class Solution {24 public:25 26     int maxPoints(vector<Point> &points) {27         if(points.size()==0) return 0;28 29         int last_x = (points.begin()->x) - 1;30         int maxnum = INT_MIN,curnum = 0;31         std::sort(points.begin(),points.end(),typeisless);32         for(vector<Point>::iterator iter = points.begin();33             iter != points.end();++iter){34             if(iter->x == last_x){35                 ++curnum;36             }else{37                 last_x = iter->x;38                 curnum = 1;39             }40 41             maxnum = maxnum<curnum?curnum:maxnum;42         }43 44         unordered_map<double,int> count_map;45         count_map.insert(pair<double,int>(0.0,0));46 47         for(vector<Point>::iterator iter1 = points.begin();48             iter1 != points.end();++iter1){49             count_map.clear();50             int samepointnum = 0;51 52             for(vector<Point>::iterator iter2 = iter1 + 1;53                 iter2 != points.end();++iter2){54 55                 if(iter2->x == iter1->x && iter2->y == iter1->y){56                    ++samepointnum;continue;57                 }else if(iter2->x == iter1->x)58                     continue;59                 else{60                     double dslope = (static_cast<double>(iter2->y - iter1->y))/61                                     (static_cast<double>(iter2->x - iter1->x));62                     if(count_map.find(dslope) != count_map.end()) ++count_map[dslope];63                     else{64                         count_map[dslope] = 1;65                         ++count_map[dslope];66                     }67                 }68             }69 70             for(unordered_map<double,int>::iterator iter=count_map.begin();71                 iter!=count_map.end();++iter){72                 if(iter->second + samepointnum > maxnum){73                     maxnum = iter->second + samepointnum;74                 }75             }76         }77 78         return maxnum;79     }80 };