SPOJ 8725. Closest Point Pair

Here isthe problem statement
http://www.spoj.com/problems/CLOPPAIR/

The constraints are N<=50000. The most obvious approach is to use brute force in other words for every coordinated run over the others and update the answer if possible. This takes N^2 time which won't pass the time limit. Here is what I suggest. We will do just something like this but  with a little "saving". First lets sort our coordinates by x. Suppose we have a variable ANS where we store the minimum distance. Ok . Now we take the first coordinate in a sorted array . And we start comparing it to others. Here is the pseudocode

for(i=1;i<n;i++)
   for(j=i+1;j<=n;j++)
     compare distance of coordinate i and corrdinate j and update the answer.

By just adding one more if statement we can get our code to work in way shorter time. As we know the distance between every pair of coordinates is sqrt (  sqr(x1-x2)+sqr(y1-y2) ). I recommend not using the sqrt function every time. We will use it in the end for outputing the answer, the sqrt function is slow and we might lose the correctness in it. So, back to our problem, we check if current distance between Xs of 2 corrdinates squared is gerater then the answer we have so far we brake the loop because the higher the index J becomes the higher X .
Here is how it looks
 for(i=1;i<n;i++)
   for(j=i+1;j<=n;j++)
    {
         if( sqr( a[i].x-a[j].x) >ans)
             break;
     compare distance of coordinate i and corrdinate j and update the answer.
    }
This will save us significant amount of time, its enough to get the time limit passed. Check teh source code for clarification.

       DOWNLOAD THE FULL SOURCE CODE