Editorial for Facebook Hacker Cup '15 Round 3 P1 - Boomerang


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Since your score is the product of the number of targets hit on each segment, we need to attempt to hit at least one target on the initial segment. So we'll throw the boomerang in the direction of some target. For each target, we can determine the intermediate point at which the boomerang changes direction (after D distance). From that point, we will again want the boomerang to fly towards at least one target.

A naive solution takes \mathcal O(N^3) time. There are N possible directions in which to throw the boomerang, each of which yields a possible intermediate point for the boomerang's path. For each such point, there are N possible directions for the second segment, and it takes \mathcal O(N) time to determine, for each of those possible angles from the intermediate point, which of the targets lie on that path.

We can do better for each possible considered intermediate point if we sort the targets by angle relative to that point, in \mathcal O(N \log N) time. We can then do an angular line sweep to determine, in \mathcal O(N) time, how many targets lie along each distinct possible considered angle relative to the intermediate point. This yields a time complexity of \mathcal O(N^2 \log N).


Comments

There are no comments at the moment.