leetcode149 直线上最多的点数

思路：

哈希表。

实现：

 1 class Solution
 2 {
 3 public:
 4     int maxPoints(vectorint>>& points)
 5     {
 6         int n = points.size();
 7         int res = 1;
 8         for (int i = 0; i < n; i++)
 9         {
10             int x0 = points[i][0], y0 = points[i][1];
11             unordered_map<int, int> mp;
12             for (int j = 0; j < n; j++)
13             {
14                 if (j == i) continue;
15                 int x1 = points[j][0], y1 = points[j][1];
16                 int x = x0-x1, y = y0-y1;
17                 int g = __gcd(x, y);
18                 x /= g; y /= g;
19                 if (x == 0) y = 1;
20                 if (y == 0) x = 1;
21                 if (x < 0)
22                 {
23                     x = -x; y = -y;
24                 }
25                 int val = x * 20001 + y;
26                 if (!mp.count(val)) mp[val] = 0;
27                 mp[val]++; 
28             }
29             for (auto it: mp)
30             {
31                 res = max(res, it.second+1);
32             }
33         }
34         return res;
35     }
36 };