I stumbled across this problem : 

> 
> "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
> 
> 
> 

[![enter image description here](https://i.stack.imgur.com/ocHmy.jpg)](https://i.stack.imgur.com/ocHmy.jpg)
Actually, the problem requires the maximum number of collinear points that includes the tourist coordonates. 

I've found a solution that is 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++; 
  ...
}

```

But I'm pretty sure that it can be done better than O(k^2). I didn't find any optimizations yet.