Maximum number of collinear points - optimization

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

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.