时间戳

首页 > 解决方案 > 无论如何，为了避免线上最大点数问题的浮点运算

c++ - 无论如何，为了避免线上最大点数问题的浮点运算

问题描述

我正在尝试解决 Leet 代码上的“Max Points on Line”问题。我不可避免地需要进行浮点运算来计算每条线的 Y-Intercept 和斜率。由于我过去的糟糕经历，我试图尽可能避免浮点运算。你有什么建议我可以在这里做到吗？

我正在使用 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，这是不准确的。如果可能的话，我试图避免浮点除法。

注意：Max Points on a Line 问题是给定二维空间中的点（在这种情况下为整数坐标），并找到一条线上的最大点数。例如，如果点是 (0,0)、(2,2)、(4,3)、(1,1)，则答案是 3，即点 (0,0)、(1,1) 和 (2) ,2)

标签： c++precisioncomputational-geometry

解决方案

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

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

假设坐标的范围需要N位，则增量的计算需要N+1位，而表达式的精确评估需要2N+2位更差。您对此无能为力。

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

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

推荐阅读