c - 共线点的最大数量-优化

我偶然发现了这个问题：
“旅游者有一张m x n的地图，地图上画着k
城市（k（lin游客决定朝某个方向走，在边缘停下来
地图上的。但他想沿着让他走路的方向走
通过尽可能多的城市。你必须计算最大值。
他可以访问的城市数量。”
m，nK例如5 10（m和n）
32（游客坐标）
7（k=城市数量）
0 0（城市坐标）
0 8个
16个
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）更好。我还没有找到任何优化。

最佳答案

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