c++ - 无论如何要避免最大点在线问题上的浮点运算

我正在尝试解决Leet代码上的“在线最大点数”问题。我不可避免地需要进行浮点运算来计算每条线的Y截距和斜率。由于过去的不良经验，我正在尝试尽可能避免浮点运算。您有什么建议我可以在这里吗？

我使用LeetCode框架进行开发，几乎可以访问标准C++库。
使用double或long double进行了尝试，但是其中一个测试用例已经将数字推到了这些数据类型的准确性极限。

//P1[0] is X coordinate for point P1 and P1[1] is Y coordinate

long double slopeCalc( vector<int> &p1, vector<int> &p2 )
{
    if( p1[0] == p2[0] && p1[1] == p2[1] )
    {
        return DBL_MIN;
    }

    if( p1[0] == p2[0] && p1[1] != p2[1] )
    {
        return DBL_MAX;
    }

    return ( (long double)p2[1] - (long double)p1[1] ) / ((long double)p2[0] - (long double)p1[0]);
}

long double yIntersectionCalc( vector<int> &p1, vector<int> &p2 )
{
    if( p1[0] == p2[0] && p1[1] == p2[1] )
    {
        return DBL_MIN;
    }

    if( p1[0] == p2[0] && p1[1] != p2[1] )
    {
        return DBL_MAX;
    }

    return ((long double)p1[1]*(long double)p2[0] - (long double)p2[1]*(long double)p1[0]) / (long double)(p2[0] - p1[0]);
}

如果两个点分别是(0，0)和(94911150，94911151)，则斜率计算为1，这是不准确的。我试图避免浮点除法。

注意:将在2D空间中给定点上的最大点问题(在这种情况下为整数坐标)，并找到一条线上的最大点数。例如，如果点是(0,0)，(2,2)，(4,3)，(1,1)，则答案是3，分别是点(0,0)，(1,1)和(2 ，2)

最佳答案

在整数坐标中，可以将三点的对齐测试写为表达式

(Xb - Xa) (Yc  - Ya) - (Yb - Ya) (Xc - Xa) = 0

假设坐标范围需要N位，则增量的计算将使用N+1位，而对表达式的精确求值则需要2N+2位。您对此无能为力。

在您的情况下，64位整数应该足够了。

一条建议:避免使用斜率/截距表示法。

关于c++ - 无论如何要避免最大点在线问题上的浮点运算，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56398115/