Cod sursa(job #2280525)

Utilizator Garen456Paun Tudor Garen456 Data 10 noiembrie 2018 19:06:12
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.55 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");

const int Nmax = 100002;

struct Point
{
    int x,y;
} A[Nmax] , B[Nmax] , C[Nmax ];

bool CompX( Point a , Point b )
    {  return a.x<b.x;  }

bool CompY (   Point a , Point b)
      {  return a.y<b.y; }

long long Distance ( Point a , Point b)
   {
       return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
   }

long long Solve ( int left , int right )
{
    if ( right - left + 1 <= 3 )
    {
        sort ( A + left , A + right + 1 , CompY  );

       long long  LeastDist = (  (long long)A[left].x -  (long long ) A[left+1].x  ) * (  (long long)A[left].x -  (long long ) A[left+1].x  )  + (  (long long)A[left].y -  (long long ) A[left+1].y  ) * (  (long long)A[left].y -  (long long ) A[left+1].y  );

        for ( int i=left ; i < right ; ++i)
            for( int j=i+1 ; j<=right ;++j)
        { long long  Dist = (  (long long)A[i].x -  (long long ) A[j].x  ) * (  (long long)A[i].x -  (long long ) A[j].x  )  + (  (long long)A[i].y -  (long long ) A[j].y  ) * (  (long long)A[i].y -  (long long ) A[j].y  ) ;
          if ( LeastDist > Dist )
                LeastDist = Dist ;
        }

      return LeastDist;

    }

    else
    {

        int Middle = (left + right ) / 2;
        Point Mid;
        Mid.x = A[Middle].x;
        Mid .y = 0 ;

        long long LeastDist1 = Solve ( left , Middle ) ;
        long long LeastDist2 = Solve ( Middle + 1 , right ) ;
        long long LeastDist = min(LeastDist1 , LeastDist2 );

        int i ,j ,k = 0 , h = 0;
        for ( i = left , j =Middle +1 ; i<= Middle || j<=right ; )
            if (  i<=Middle &&  ( ( A[i].y < A[j].y )  || j > right ) )
                 B[ ++k ] = A[ i++] ;
            else if ( j<=right )
                 B[++k] = A[j++];


        for (i=1 , j = left  ;i<=k && j<= right ;++i ,++j)
        {if (  Distance( Mid , B[i] )  <= LeastDist )
              C[++h] = B[i];
         A[j]=B[i];
        }

        for (i=1; i< h;++i)
            for (j=i+1;j<=i+7;++j)
        {   long long Dist = Distance(C[i],C[j]);
            if (  Dist < LeastDist )
                LeastDist = Dist ;
        }
        return LeastDist;
    }

    return 0;
}


int main()
{

    int N ;
    long long result ;
    fin>>N;

    for ( int i = 1;  i <= N ; ++i )
         fin>>A[i].x>>A[i].y;

    sort(A+1,A+N+1,CompX);

    result = Solve(  1 , N );



    fout<< setprecision(6) << fixed <<sqrt ( (double) result) ;

    return 0;
}