This problem is from the recently concluded Facebook Hackercup 2016 Qualification round. You can take a look at the problem statement in this link.
I am giving the abridged problem statement here. Given a set of coordinates in a 2D-plane, We have to find out the total number of pairs of lines with equal length and also share one end point.
For example, let us take the points {(0,0), (0,1), (1,0)}
, there is one pair of lines, with a distance of 1. The line between (0,0), (0,1)
and the line between (0,0), (1,0)
.
The simplest way to solve this problem is this. Take a point (x,y) and try to calculate the distance to every other point. Maintain a map of distance to the number of other end points with that distance. This is O(n2 log n) solution.
Here is the C++ code for the same.