Cod sursa(job #781520)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 24 august 2012 16:28:21
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define PDD pair< double, double >
#define mp make_pair
#define x first
#define y second
#define NMAX 100005
#define INF 4e18
using namespace std;
PDD X[NMAX], Y[NMAX], Aux[NMAX];
int n, i, j, lg;
inline double Dist( const PDD &A, const PDD &B ){
  return sqrt( ( A.x - B.x )*( A.x - B.x ) + ( A.y - B.y )*( A.y - B.y ) );
}
inline double Sol( int St, int Dr ){
  if( Dr == St + 1 ) return INF;
     else if( Dr == St + 2 ){
              if( Y[St] > Y[Dr - 1] ) swap( Y[St], Y[Dr - 1] );
               return Dist( X[St], X[Dr - 1] );
            }
    int M = (St + Dr)>>1;
    double DistMin = min( Sol( St, M ), Sol( M, Dr ) );
    merge( Y + St, Y + M, Y + M, Y + Dr, Aux );
    copy( Aux, Aux + ( Dr - St ), Y + St );
     lg = 0;
     for( i = St; i < Dr; ++i )
      if( abs( X[M].x - Y[i].y ) <= DistMin )Aux[ lg++ ] = Y[i];
    for( i = 0; i < lg - 1; ++i )
     for( j = i + 1; j < lg && j - i < 8; ++j )
    DistMin = min( DistMin, Dist( Aux[i], Aux[j] ) );
  return DistMin;
}
int main(){
   ifstream fin("cmap.in");
   ofstream fout("cmap.out");
   fin>>n;
    for( i = 0; i < n; ++i )fin>>X[i].x>>X[i].y;
   sort( X, X + n);
    for( i = 0; i < n; ++i )Y[i] = mp( X[i].y, X[i].x );
   fout<<fixed<<setprecision(6)<<Sol( 0, n );
return 0;
}