Given n points, how can I find the number of points with given distance-CodePudding

I have an input of n points (X,Y) that are between 0 and 2^32 inclusive.
I need to create an algorithm that finds the number of pairs of points with a distance of 2018.
I have thought of checking with every other point but it would be O(n^2) and I have to make it more efficient.
I also thought of using a set or a vector and sort it using a comparator based on the distance with the origin point but it wouldn't help at all.
So how can I do it efficiently?
note: I'm coding it in c

CodePudding user response：

You could try using a

The complexity of this is probably O(n*log(n)) but don't pin me down on that.

One additional word on the distance calculation: You are probably much faster if you don't do

dx = p1x - p2x;
dy = p1y - p2y;
if ( sqrt(dx*dx   dy*dy) == 2018 ) {
    ...
}

but

dx = p1x - p2x;
dy = p1y - p2y;
if ( dx*dx   dy*dy == 2018*2018 ) {
    ...
}

Squaring is faster than taking the sqare root. So just compare the square of the distance with the square of 2018.

CodePudding user response：

Let me give you a piece of advise:

The distance between two points (X1, Y1) and (X2, Y2) equals:

sqrt((X2 - X1)^2   (Y2 - Y1)^2)

So, you might think to check:

sqrt((X2 - X1)^2   (Y2 - Y1)^2) <= 2018

However, you can easily simplify this as:

(X2 - X1)^2   (Y2 - Y1)^2 <= 2018^2  // or:
(X2 - X1)^2   (Y2 - Y1)^2 <= 4072324

Here you have already dropped the calculation of a square root, which is a performance killer.

Next to that, there's the simple observation that, if either X- or Y-coordinates are more than 2018 from each other, then the distance will surely be larger than 2018, so, you might do something like:

boolean close_enough (double X1, Y1, X2, Y2)
{
    if ((abs(X2 - X1) > 2018) || (abs(Y2 - Y1) > 2018))
      return false;
    else
      return ((X2 - X1)^2   (Y2 - Y1)^2 <= 4072324);
}

As you see, performance optimisation is not only a matter of big-O notation :-)