c++algorithmsortingcoordinatesdistance

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


I have an input of n unique points (X,Y) that are between 0 and 2^32 inclusive. The coordinates are integers.

I need to create an algorithm that finds the number of pairs of points with a distance of exactly 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?


Solution

  • There is one Pythagorean triple with the hypotenuse of 2018: 11182+16802=20182.

    Since all coordinates are integers, the only possible differences between the coordinates (both X an Y) of the two points are 0, 1118, 1680, and 2018.

    Finding all pairs of points with a given difference between X (or Y) coordinates is a simple n log n operation.

    Numbers other than 2018 might need a bit more work because they might be members of more than one Pythagorean triple (for example 2015 is a hypotenuse of 3 triples). If the number is not given as a constant, but provided at run time, you will have to generate all triples with this hypotenuse. This may require some sqrt(N) effort (N is the hypotenuse, not the number of points). One can find a recipe on the math stackexchange, e.g. here (there are many others).