最大共线点数 - 优化

Question

我偶然发现了这个问题：

"A tourist have a map of dimensions M x N. On the map are plased k cities (k<=2000). Cities' coordinates have that form (lin, col) (lin<=M and col<=N). We know the tourist's coordinates as well. The tourist decided to take in a certain direction and to stop at the edge of the map. But he wants to walk on the direction that makes him walk through as many cities as posible. You have to calculate the maximum number of cities that he can visit."

M, N <= 1000

K<=2000

e.g. 5 10 (M and N)

3 2 (tourist's coordinates)

7 (k = number of cities)

0 0 (coordinates of the cities)

0 8

1 6

2 2

2 4

3 7

4 5

Answer : 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) 中完成此操作。以游客的坐标为原点，如果线 (t,k1) 和 (t,k2) 具有相同的斜率，则两个城市 k1 和 k2 共线。如果您按斜率将 k 值存储在散列中，这只需要遍历所有 k，然后再遍历计算出的斜率以找到 ks 最多的斜率。

最大共线点数 - 优化

Maximum number of collinear points - optimization

c

algorithm

optimization

coordinate-systems