|
原问题： 已知两个数组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;
}
|