Close

Facebook Hackercup 2016- Boomerang constellations problem solution

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.

Leave a Reply

Your email address will not be published. Required fields are marked *