Cod sursa(job #980810)

Utilizator superman_01Avramescu Cristian superman_01 Data 5 august 2013 18:05:13
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<fstream>
#include<algorithm>
#define oo (4e18)
#define NMAX 100005
#include<cmath>
 
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
 
struct point
{
    int x , y ;
}v[NMAX];
int N;
point pos[NMAX];
int k;
 
inline long long real ( long long A )
{
    if( A < 0 )
        return -A ;
    else
        return A;
}
inline long long dist ( point A , point B )
{
    return real ( ( A.x - B.x) ) *real ( ( A.x -B.x) ) +  real ( ( A.y-B.y ) )  *real ( ( A.y-B.y ) );
}

bool comp ( point A , point B )
{
	return A.y < B.y;
}
long long DEI(int st ,int dr)
{
    long long a,b;
    long long x ; 
    int i , ii;
    int m = (st + dr ) / 2;
    if(st >= dr )
        return oo;
    if( dr-st==1 )
        return dist(v[st],v[dr]);
    a=DEI( st , m ) ;
    b=DEI( m + 1 , dr ) ;
    x=min(a,b);
    k = 0 ;
    for(  i = st ; i <= dr ; ++i )
        if( real(v[m].x - v[i].x) < x )
            pos[++k] = v[i];
	sort( pos +1 , pos + k +1 , comp );
    for( i = 1 ; i < k ; ++i )
      for( ii = i+1  ; ii <= i+8 && ii <= k ; ++ii )
         x = min(x,dist ( v[i], v[ii] )) ;
       
     return x ;
}
bool cmp ( point  A , point B )
{
	return A.x < B.x ;
}
 
int main ( void )
{
    int i ;
    long long Answer ;
    f>>N;
    for( i = 1 ; i <= N ;  ++i )
        f>>v[i].x>>v[i].y;
    sort(v+1,v+N+1 ,cmp) ;
    Answer = DEI(1,N);
    g.precision(7);
    g<<fixed<<sqrtl(Answer ) ;
}