Any idea for O(n log n) solution of http://www.spoj.pl/problems/GANNHAT/?

I have tried spo开发者_高级运维j problem http://www.spoj.pl/problems/GANNHAT/ but my O(n^2) solution is giving TLE.Can anyone give me some idea of some O(n log n) solution for this problem.I'm not abled to figure out how it can be done in O(n log n).Thanx in advance..

Use a KD-Tree. This question should point you in the right direction.

I've got a solution, the complexity can be O(nlogn) at best but O(n^2) at worst.

It is based on the quadtrees. Once you've built your tree, it is simple to know what is the closest point to a particular point Ai, just iterate over the neighbours. You don't have to iterate "far", because as soon as you find a point Aj in the neighboring cells, you can eliminate most of the other points in the more distant cells.

Edit : Well, I've just seen Jeff answer, and quadtrees are just KD-Trees with K=2, but they fit your question because the points are in 2D =)