最大共线点数-优化

Question

我偶然发现了这个问题：

“游客的地图上有一张can维的地图，地图上有k个城市(k<=2000)。城市的坐标有那个形式(林、科尔) (lin<=M和col<=N)。我们也知道游客的坐标。游客决定沿着一定的方向走，在地图的边缘停下来。但他想沿着这个方向走，这样他就能走到尽可能多的城市。你必须计算出他能去的城市的最大数量。” M，N <= 1000 K<=2000 例如5、10 (M和N) 3 2(游客坐标) 7 (k =城市数目) 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)做得更好。我还没有找到任何优化。

Answer 1

计算由旅行者和每个点的坐标确定的直线的斜率。你现在有一系列的斜坡。现在您可以对这个数组进行排序，并查看哪个斜率出现次数最多。或者您可以散列斜率(以避免对数组进行排序)。

Answer 2

你可以在O(n)中这样做。当k1和k2的直线(t，k1)和(t，k2)具有相同的斜率时，以旅游坐标为原点的两个城市是共线性的。如果按斜率将k值存储在散列中，这只需要一次遍历所有k，然后一次通过计算出的斜率来查找具有最大k值的斜率。