CERC 2008 : In case of failure

Revision en1, by ko_osaga, 2016-06-22 07:38:18

http://www.spoj.com/problems/FAILURE/

Problem is simple : N points are given in Euclidean plane. For each points, you should find the smallest distance between itself and other points, in respect of euclidean distance.

I had no idea on the solution of this problem (except Delaunay triangulation. I hope there's a simpler solution), so I googled for the solution : https://github.com/anurag-jain/spoj-1/blob/master/MLE.cpp but I still have no idea why it's O(NlgN).

Can someone help me with this problem? T.T

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ko_osaga 2016-06-22 07:38:18 547 Initial revision (published)