斜率问题
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 map<double, int> S; 14 if (points.size() == 0) return 0; 15 int ans = 1; 16 for (int i = 0; i < points.size()-1; i++) { 17 int num = 1; 18 int samep = 0; 19 S.clear(); 20 for (int j = i+1; j < points.size(); j++) { 21 double k = numeric_limits<double>::infinity(); 22 if (points[j].x != points[i].x) k = (double)1.0*(points[j].y-points[i].y)/(points[j].x-points[i].x); 23 else if (points[j].y == points[i].y) {samep++; continue;} 24 if (S.count(k)) S[k]++; 25 else S[k] = 2; 26 num = max(num, S[k]); 27 } 28 ans = max(ans, num+samep); 29 } 30 return ans; 31 } 32 };
C#
1 /** 2 * Definition for a point. 3 * public class Point { 4 * public int x; 5 * public int y; 6 * public Point() { x = 0; y = 0; } 7 * public Point(int a, int b) { x = a; y = b; } 8 * } 9 */ 10 public class Solution { 11 public int MaxPoints(Point[] points) { 12 Dictionary<double, int> S = new Dictionary<double, int>(); 13 if (points.Length == 0) return 0; 14 int ans = 1; 15 for (int i = 0; i < points.Length-1; i++) { 16 int num = 1; 17 int samep = 0; 18 S = new Dictionary<double, int>(); 19 for (int j = i+1; j < points.Length; j++) { 20 double k = double.PositiveInfinity; 21 if (points[j].x != points[i].x) k = (double)1.0*(points[j].y-points[i].y)/(points[j].x-points[i].x); 22 else if (points[j].y == points[i].y) { 23 samep++; 24 continue; 25 } 26 if (S.ContainsKey(k)) S[k]++; 27 else S.Add(k, 2); 28 num = Math.Max(num, S[k]); 29 } 30 ans = Math.Max(ans, num + samep); 31 } 32 return ans; 33 } 34 }