leetcode 149. Max Points on a Line

149. 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.

  1、遍历每一个点，作为基准点
  2、其他点与之比较，用map来存斜率，特殊考虑 垂直和复制的情况。 

现在有一个数据过不了，网上很多其他人代码也过不了。

/**
 * 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:
    
    int maxPoints(vector<Point>& points) 
    {
        if (points.size() <= 2)
            return points.size();
       
        int ret = 2;
        for(int i = 0; i < points.size(); i++)
        {
            int dup = 0;
            int ver = 0;
            int curcount = 1;
            map<long double,int> xielv;
           
            for(int j=0;j<points.size();j++)
            {
                if(i != j)
                {
                    double _x = points[i].x - points[j].x;
                    double _y = points[i].y - points[j].y;
                   
                    if(_x == 0 && _y == 0)//两个点相同
                        dup++;
                    else if(_x == 0)//垂直情况
                    {
                        if(ver == 0)
                            ver = 2;
                        else
                            ver++;
                        curcount = max(curcount, ver); 
                    }
                    else//斜率存在的情况
                    {
                        long double xie = _y / _x;
                        if(xielv[xie] == 0)
                            xielv[xie] = 2;
                        else
                            xielv[xie]++;
                        curcount = max(curcount, xielv[xie]);
                    }
                }
            }
            ret = max(ret, curcount + dup);
       }
       return ret;  
    }
};