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.

思路：

这道题的数据好像很弱，我只用了最普通的方法居然可以AC。

对于每个点，求其他点到他连线的斜率，如果斜率相同，就表示在同一条直线上，用hash记录斜率和点的数目的关系。复杂度是O(n^2)的。

最开始出错是因为没有考虑重复点的情况，加上这方面判断就AC了。

代码：

 1     int maxPoints(vector<Point> &points) {
 2         int n = points.size();
 3         if(n <= 2)
 4             return n;
 5         map<float, int> slope;
 6         map<pair<int, int>, bool> visited;
 7         int res = 1;
 8         int duplicate;
 9         for(int i = 0; i < n; i++){
10             slope.clear();
11             if(visited.find(pair<int, int>(points[i].x, points[i].y)) != visited.end())
12                 continue;
13             visited[pair<int, int>(points[i].x, points[i].y)] = true;
14             duplicate = 0;
15             int tres = 1;
16             for(int j = 0; j < n; j++){
17                 if(j == i)
18                     continue;
19                 if(points[i].x == points[j].x && points[i].y == points[j].y){
20                     duplicate++;
21                     continue;
22                 }
23                 float tmp;
24                 if(points[i].x == points[j].x)
25                     tmp = INT_MAX;
26                 else
27                     tmp = (float)(points[i].y-points[j].y)/(float)(points[i].x-points[j].x);
28                 if(slope.find(tmp) == slope.end())
29                     slope[tmp] = 2;
30                 else
31                     slope[tmp]++;
32                 tres = tres > slope[tmp] ? tres : slope[tmp];
33             }
34             res = res > tres+duplicate ? res : tres+duplicate;
35         }
36         return res;
37     }