[LeetCode 第5题] -- Max Points on a Line

题目链接: Max Points On a Line

题目意思: 在二维平面上，有n个点，求同一条直线上最多点的个数

题目分析: 1. O(n^2)直接暴力求每个点所在所有直线的最大值，利用map来映射

                2. 有个wa点有可能重复出现，比如(1,1) 和 (1,1)应该算两个

代码：

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
     bool isEqual(Point &a, Point& b);
     int getMaxPoints(map<double, int> &mp);
     int maxPoints(vector<Point> &points);
};

bool Solution::isEqual(Point &a, Point& b) {
     if (a.x == b.x && a.y == b.y) {
	return true; 
     }
     return false;
}
int Solution::getMaxPoints(map<double, int> &mp) { 
     int maxNum = 0; 
     for (map<double, int>::iterator it = mp.begin(); it != mp.end(); ++it) {
	  maxNum = max(maxNum, it->second);
     }
     return maxNum;
}
int Solution::maxPoints(vector<Point> &points) {
     int ansMaxPoints = 0; 
     int numPoints = points.size();
     if (numPoints <= 2) {
 	return numPoints;
     }
     map<double, int> mp;
     const double MAXN = 1.0* (1 << 30);
     const double MIN = 0.0;
     for (int i = 0; i < numPoints; ++i) {
	 mp.clear();
	 int samePoints = 1;
	 for(int j = 0; j < numPoints; ++j){
	     if (i == j) {
		continue;
	     }
	     if (isEqual(points[i], points[j])) {
		samePoints++;
		continue;
	     }
	     double key = 0.0;
	     if (points[i].x == points[j].x) {
	        key = MAXN;
	     }
	     else if (points[i].y == points[j].y) {
		key = MIN;
	     }
	     else {
	        key = 1.0*(points[i].y-points[j].y)/(points[i].x-points[j].x);
	     }
	     mp[key]++;
	}
	ansMaxPoints = max(ansMaxPoints, getMaxPoints(mp)+samePoints);
     }
     return ansMaxPoints;
}