Max Point on a line

 1 /**
 2  * Definition for a point.
 3  * struct Point {
 4  *     int x;
 5  *     int y;
 6  *     Point() : x(0), y(0) {}
 7  *     Point(int a, int b) : x(a), y(b) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int maxPoints(vector<Point> &points) {
13         
14         /*找到一条直线上最大数目的点,返回这条直线*/
15         if(points.size()<3)
16             return points.size();
17         
18        
19         int maxNum=0; map<double,int> slope_count;
20         /*以点为中心，计算其他n-1点与之斜率，之中挑选出最大点的斜率点*/
21         for(int i=0;i<points.size();i++)
22         
23          {
24             int cnt=0;//b表示重合点数
25              slope_count.clear();
26             for(int j=i+1;j<points.size();j++)
27              {
28                 
29                   if(i==j) continue;
30                 
31                 /*点是不是重合点*/
32                 
33                 if(points[i].x == points[j].x && points[i].y == points[j].y)
34                 {
35                     cnt++;
36                     continue;
37                 }  
38                 
39                 /*判断斜率，注意与Y轴平行的*/
40                 
41                 double slope=points[i].x==points[j].x ? INT_MAX:(double)(points[j].y - points[i].y)/(points[j].x - points[i].x); 
42                 
43                 slope_count[slope]++;
44             }
45             
46         
47         
48         /*对其进行比较*/
49          if(slope_count.size()==0)
50                slope_count[INT_MIN]=0;/*所有点与Y轴平行*/
51         
52          map<double,int>::iterator it = slope_count.begin();
53          
54          for(;it!=slope_count.end();it++)
55               {
56                         if(it->second+cnt>maxNum)
57                             maxNum=it->second+cnt;
58             
59                }
60         }
61         /*最开始并没有记录其开始点，所有最后+1*/
62         return maxNum+1;
63     }
64 };