同一直线上的点

Question

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

我的方法:- 我试图维护一个以斜率作为键的散列图，我想获得最大的第二个值以获得相同[上的最大点数=29=]像这样

      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 时，我得到运行时间 error.I 也尝试了 atan(slope) 这样我就可以获得学位而不是一些未定义的值，但仍然无法正常工作。

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

P.S -我的母语不是英语所以如果有什么问题请忽略够了请告诉我

Answer 1

你的方法很新颖！

然而，垂直线具有无限斜率，这就是这里的问题：不允许除以 0。

基于您的解决方案（斜率）的备选方案：

...
int mpvertical=0;   // a separate couner for verticals
if (xi-x0) 
   mp[(yi-y0)/(xi-x0))]++;
else if (yi-y0)    
   mpvertical++;  
// else the point (xi,yi) is the point (x0,y0):  it shall not be counted)

这很麻烦，因为您拥有地图中的所有内容以及这个额外的计数器。但这将是准确的。一种解决方法是计算 mp[std::numeric_limits<double>::max()] 中的此类点，但这将是一个近似值。

备注：案例是 xi==x0 AND yi==y0 对应于您的原点。这些点必须被丢弃，因为它们属于每条线。

三角函数（角度）：

这里使用了一般的atan2 formula用来将笛卡尔坐标转为极坐标，得到角度：

if (xi!=x0 && yi!=y0)  // the other case can be ignored 
    mp[ 2*atan((yi-y0)/((xi-x0)+sqrt(pow(xi-x0,2)+pow(yi-y0,2)))) ]++;

所以你的 mp 键将是 -pi 和 +pi 之间的角度。没有更多的额外案例，但稍微多了一些计算。

您可以隐藏这些额外的细节并使用稍微更优化的build in function：

if (xi!=x0 && yi!=y0)  // the other case can be ignored 
    mp[ atan2(yi-y0, xi-x0) ]++;

Answer 2

你可以试试这个方法

struct vec2
{
   vec2(float a,float b):x(a),y(b){}
   float x,y;
};

bool isColinear(vec2 a, vec2 b, vec2 c)
{
   return fabs((a.y-b.y)*(a.x-c.x) - (a.y-c.y)*(a.x-b.x)) <= 0.000001 ;
}

Answer 3

移动所有东西，使零点在原点：

(x_i, y_i) -= (x₀, y₀)

然后对每个点(x_i,y_i)求x_{i的最大公约数} 和 y_i 并将两个数字除以它：

k = GCD(x_i, y_i)
(x_i', y_i`) = (y_i/k, y_i/k)

现在，位于同一条射线上的点将映射到 相等的 个点。如果 (x_i, y_i) 与 (x_j, y_j) 然后 (x_i', y_i') = (x_j', y_j').

现在求最大的等分集（别忘了任意(x_i, y_i) = (0, 0)) 你就有了答案。

Answer 4

我假设没有其他点与您的坐标相同 "origin"。

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

斜率是 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() 的 return 值作为您的地图键。

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

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

Answer 5

你已经接受了一个答案，但我还是想分享我的方法。该方法利用了三个点 a、b 和 c 是协变的当且仅当

(a.first-c.first)*(b.second-c.second) - (a.second-c.second)*(b.first-c.first) == 0

您可以使用这个属性来创建一个像这样的自定义比较对象

struct comparePoints {
   comparePoints(int x0 = 0, int y0 = 0) : _x0(x0), _y0(y0) {}

   bool operator()(const point& a, const point& b) {
      return (a.first-_x0)*(b.second-_y0) - (b.first-_x0)*(a.second-_y0) < 0;
   }

private:
   int _x0, _y0;
};

然后您可以根据

将其用作地图的比较对象

comparePoints comparator(x0, y0);
map<pair<int, int>, int, comparePoints> counter(comparator);

然后您可以像之前一样向这张地图添加点：

if (!(x == x0 && y == y0))
    counter[{x,y}]++;

通过使用comparitor作为比较对象，map中的两个键a、b如果!comparator(a, b) && !comparator(b,a)被认为是相等的，当且仅当a、b 和 {x0,y0} 共线。

这种方法的优点是不需要对坐标进行除法，避免了舍入误差和除以零的问题，也不需要计算atan，这是一个代价高昂的操作。

同一直线上的点

Points on the same line

c++

geometry

maps

runtime-error