Clever Geek Handbook

Maximum Collinear Points - Optimization

I came across this problem:

"The tourist has a map of sizes M x N. There are k cities on the map (k <= 2000). The coordinates of the cities have the following form (lin, col) (lin <= M and col <= N). We also know the tourist coordinates . the tourist has decided to take in a certain direction and stop at the edge of the map. But he wants to go in a direction that makes him walk through as many cities as possible. You must calculate the maximum number of cities he can visit. "

M, N <= 1000

K <= 2000

eg. 5 10 (M and N)

3 2 (tourist coordinates)

7 (k = number of cities)

0 0 (city coordinates)

0 8

sixteen

2 2

2 4

3 7

4 5

Answer: 3

enter image description here In fact, the problem requires the maximum number of collinear points that include the tourist coordinates.

I found a solution which is O (k ^ 2).

for(i=0; i<k; i++) {
    fscanf(fi, "%d%d", &lin[i], &col[i]);
    lin[i]-=l; //we consider tourist 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 it can be done better than O (k ^ 2). I haven't found any optimizations yet.

+3


source to share


2 answers


You calculate the slope of the line defined by the coordinates of the traveler and each point. You now have an array of slopes. Now you can order this array and see which one has the most time. Or you can hash the slopes (to avoid sorting the array).



+3


source


You can do this in O (n). With tourist coordinates defined as the origin, two cities k1 and k2 are collinear if the lines (t, k1) and (t, k2) have the same slope. If you store your k values ​​in a slope hash, it only requires one pass through all k and then one pass through the slopes calculated to determine the slope with the highest ks.



+2


source






More articles:


All Articles