c - 最大共线点数 - 优化

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

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