算法（40）-直线斜率-C++

原问题： 已知两个数组arrx arry 表示二维平面上的点坐标
              问一条线最多能穿过多少个点？
             其实就是问，同一斜率上的最大点数。可以简单看出一组数据的状态。
斜率计算公式 ：d=y1-y2/x1-x2 用double型数据是有精度损耗到溢出。
斜率存储：哈希表或者map表。
                 <string,int>  key表示斜率："3_5" 3/5 ；
                                     value ：表示此斜率的个数。
               返回value的最大值即可。

最大公约数计算：gcb 辗转相除法。
上代码

class Point {
public:
    int x;
    int y;

    Point()
    {
        x = 0;
        y = 0;
    }

    Point(int a, int b) {
        x = a;
        y = b;
    }
};
typedef vector<Point>  vpoint;
//最大公约数
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

//斜率， 1.最大公约数
//精度损耗
int maxPoints(vpoint points)
{
    if (points.size() == 0) {
        return 0;
    }
    if (points.size() <= 2) {
        return points.size();
    }
    //key i斜率，value 个数 
    //比如"3_4"  7
    map<string, int> mymap;//斜率表
    int result = 0;
    for (int i = 0; i < points.size(); i++)
    {
        mymap.clear();
        int samePosition = 1;//1.共位
        int sameX = 0;//2.共竖线
        int sameY = 0;//3.共横线
        int line = 0;
        for (int j = i + 1; j < points.size(); j++)
        {
            if (points[j].x == points[i].x && points[j].y == points[i].y)//1.共位
            {
                samePosition++;
            }
            else if (points[j].x == points[i].x) //2.共X
            {
                sameX++;
            }
            else if (points[j].y == points[i].y) //3.共Y
            {
                sameY++;
            }
            else              //4.共斜率
            {
                /*
                (double) p=(double)(points[i].y - points[j].y)/(double)(points[i].y - points[j].y);
                if (map.containsKey(p)) //如果原来包含这个斜率，那么值+1
                {
                    map.put(p, map.get(p) + 1);
                }
                else                    //如果没有这个斜率，则添加且值为1
                {
                    map.put(p, 1);
                }*/
                int x = points[i].x - points[j].x;
                int y = points[i].y - points[j].y;
                int m_gcd = gcd(x, y);
                //最大公约数不会丢失精度
                x /= m_gcd;
                y /= m_gcd;
                string strp = to_string(y) + "_" + to_string(x);
                if (mymap.count(strp)) //如果原来包含这个斜率，那么值+1
                {
                    auto iter = mymap.find(strp);
                    mymap.insert(make_pair(strp, iter->second + 1));
                }
                else                    //如果没有这个斜率，则添加且值为1
                {
                    mymap.insert(make_pair(strp, 1));
                }
             }
    }
      //value值出来，排序，然后取最大值
        vector<int> myvalue;
        for (auto itmap = mymap.begin(); itmap != mymap.end(); itmap++)
        {
            myvalue.push_back(itmap->second);

        }
        sort(myvalue.begin(), myvalue.end());
        int m_max = myvalue.size() - 1;
        result = myvalue[m_max];

    return result;
}