c++ - 同一直线上的点

Question

我在做一个练习题，它是这样的，我们给了 N 对坐标 (x,y)，我们也给了一个中心点，它是 (x0,y0)。我们被要求找到最大值从 (x0,y0) 穿过的直线上的点数。

我的方法:- 我试图维护一个以斜率为键的散列图，我想获得最大的第二个值以获得同一条线上的最大点数。像这样

      mp[(yi-y0)/(xi-x0))]++; //i from 0 to n

      And iterating map and doing something line this
      if(it->second >max) //it is the iterator
      max=it->second;
      and printing max at last; 

我的方法有问题- 每当我得到 (xi-x0) 为 0 时，我都会收到运行时错误。我还尝试了 atan(slope) 这样我就会得到度数而不是一些未定义的值但是仍然无法正常工作。

我的期望->如何消除这个运行时错误，我的方法是否正确，可以找到从点 (x0,y0) 穿过的直线上的最大点。

P.S -我的母语不是英语，所以如果有问题请忽略。我尽力把一切都说清楚如果我不够清楚请告诉我

Answer 1

我假设没有其他点的坐标与您的“原点”相同。

如果您所有的坐标恰好都是整数，您可以保留一个有理数数(即一对整数，即一个分子和一个分母) 作为斜率，而不是单个实数。

斜率是 DeltaY/DeltaX，因此您所要做的就是将这对数字分开。您只需要注意用它们的最大公约数 来除以该对，并处理DeltaX 为零的情况。例如:

pair<int, int> CalcSlope (int x0, int y0, int x1, int y1)
{
    int dx = abs(x1 - x0), dy = abs(y1 - y0);
    int g = GCD(dx, dy);
    return {dy / g, dx / g};
}

现在只需使用 CalcSlope() 的返回值作为您的 map 键。

如果您需要，这里有一种计算 GCD 的方法:

int GCD (int a, int b)
{
    if (0 == b) return a;
    else return gcd(b, a % b);
}