最大共线点数 - 优化

Question

我遇到了这个问题：

一个旅游者有一张 M x N 的地图。在地图上放置了 k 个城市（k <= 2000）。城市的坐标为 (lin, col)（lin <= M 和 col <= N）。我们也知道旅游者的坐标。旅游者决定朝着某个方向走，并在地图的边缘停下。但他想走一条能让他经过尽可能多城市的路线。你需要计算他能够参观的最大城市数量。

M，N <= 1000 K <= 2000

例如：5 10（M 和 N） 3 2（旅游者的坐标） 7（城市数 k） 0 0（城市坐标） 0 8 1 6 2 2 2 4 3 7 4 5 答案：3

实际上，这个问题需要包括游客坐标的共线点的最大数量。

我已经找到了一个O(k^2)的解决方案。

for(i=0; i<k; i++) {
    fscanf(fi, "%d%d", &lin[i], &col[i]);
    lin[i]-=l; //we consider tourist's coordinates the origin
    col[i]-=c;
}
for(i=0; i<k; i++) {
    points=1;
    for(j=0; j<k; j++) {
         ...
         if(lin[i] * col[j] == lin[j] * col[i]) //verify collinearity
             points++; 
  ...
}

但我相信它可以比O(k^2)更好地完成。目前我还没有找到任何优化方法。

- scummy

---

你确定这个问题等同于找到包含旅行者坐标的共线点的最大数量吗？因为如果他朝着起始位置的另一侧走一条直线，他将无法访问那些在他身后（即他起始位置的对面）的点，即使它们与他的起始位置和他正在走向的点在同一条直线上。 - Adrian

方向（如Adrian所说）可以通过一个简单的布尔值来确定。旅行者位置右侧（在x轴上）的所有点都被赋予真值，左侧的点则为假。这样你就有了（斜率，方向）作为关键字。 - cobarzan

唯一不够的情况是当一个点与旅行者的位置在同一条垂直轴上。在这种情况下，如果该点比旅行者的位置更靠北，则将方向设置为true；如果该点比旅行者的位置更靠南，则将方向设置为false。 - cobarzan

Answer 1

你需要计算由旅行者和每个点的坐标所确定的直线的斜率，这样你就得到了一个斜率数组。现在你可以对此数组进行排序，并查看哪个斜率出现次数最多。或者你可以对这些斜率进行散列（以避免排序数组）。

- cobarzan

---

一个哈希表对此至关重要。如果没有哈希表，你只能通过斜率对k进行排序，时间复杂度为O(nlogn)。 - user447688

@scummy 没问题。在这种特殊情况下，采用即兴哈希方法可能会通过所有测试用例，因为您的映射不是很大。 - cobarzan

@scummy 另外，要注意的是，在这种情况下，仅仅斜率是不够的，你还需要方向，因为在同一条直线上的某个点可能会与旅行者走的相反方向。 - cobarzan

另外，要考虑到旅行者可能直走或直下的情况，此时斜率不存在。 - Adrian

@scummy 在Adrian所说的情况下，你可以将斜率的值设置为MAX_DOUBLE（这是在你的特定情况下斜率无法达到的值，因为地图太小了）。 - cobarzan

Answer 2

您可以使用O(n)的时间复杂度完成此操作。以游客坐标为原点，如果(t,k1)和(t,k2)两个城市的线路斜率相同，则表示它们共线。如果您将k值按斜率存储在哈希表中，则只需要遍历所有k值一次，然后再遍历计算出的斜率一次，即可找到具有最多k值的斜率。

- user447688

---

谢谢回答。我将尝试实现它，只是为了熟悉哈希表。 - scummy