I tried the spoj problem http://www.spoj.pl/problems/GANNHAT/ , but my O (n ^ 2) solution gives TLE.Can, does anyone give me some idea about some O (n log n) solution for this problem. I can't figure out how this can be done in O (n log n) .Thanx in advance ..
Use KD-Tree . This question should point you in the right direction.
I have a solution, complexity can be O (nlogn) at best, but O (n ^ 2) at worst.
quadtrees. , , , Ai, . "", , Aj , .
Edit: , , - KD- K = 2, , 2D =)