算法（40） |
您所在的位置：网站首页 › 已知两点求直线方程求斜率 › 算法（40） |
|
原问题： 已知两个数组arrx arry 表示二维平面上的点坐标 问一条线最多能穿过多少个点？ 其实就是问，同一斜率上的最大点数。可以简单看出一组数据的状态。斜率计算公式 ：d=y1-y2/x1-x2 用double型数据是有精度损耗到溢出。斜率存储：哈希表或者map表。 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 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() second + 1)); } else //如果没有这个斜率，则添加且值为1 { mymap.insert(make_pair(strp, 1)); } } } //value值出来，排序，然后取最大值 vector 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; }
|
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |