Algorithms (F2008)

Hi all,
Harsh found some useful suggestions on one of the online forums: these might help. In short:

• Don’t invoke the sqrt() function till the very end (this is a hack that I use all the time in my code when doing geometric stuff). Since the sqrt() function is monotonic, the closest pair you obtain is the same whether or not you use distance or distance^2, and the sqrt() function is very expensive. You will need it at the end to report answers
• Don’t assume that inputs are integers
• There are trick inputs with a single point. Be careful not to return garbage in that case (one commenter recommended returning INFINITY)

One trick that probably doesn’t matter for getting the solution accepted, but does matter for getting the best running time: figure out when you want to stop the recursion and just use brute force. It’s comon to find that running the d&c all the way to n=1 is not the most optimized strategy.

This entry was posted on Wednesday, September 17th, 2008 at 8:57 pm and is filed under news.