Cod sursa(job #980853)

Utilizator superman_01Avramescu Cristian superman_01 Data 5 august 2013 19:04:38
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include<fstream>
#include<algorithm>
#define oo (1LL<<62)
#define NMAX 100005
#include<cmath>
#define xi first
#define y second
   
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
typedef pair < int , int > point ;
point v[NMAX] ;
int N;
point pos[NMAX];
int k;
   

inline long long dist ( point A , point B )
{
	long long a , b ;
    a= (A.xi-B.xi) ;
	a*=a ;
	b = ( A.y-B.y ) ;
	b*= b;
    return a+b ;
}
  
bool comp ( point A , point B )
{
    return A.y < B.y;
}
long long DEI(int st ,int dr)
{
    
    int m = (st + dr ) / 2;
    if(st >= dr )
        return oo;
    if( dr-st==1 )
        return dist(v[st],v[dr]);

    long long x = min ( DEI ( st , m ) , DEI( m + 1 , dr ) ) ;
    int i , ii;
    k = 0 ;
    for(  i = st ; i <= dr ; ++i )
        if( abs(v[m].xi - v[i].xi) < 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.xi < B.xi ;
}
   
int main ( void )
{
    int i ;
    long long Answer ;
    f>>N;
	
    for( i = 1 ; i <= N ;  ++i )
        f>>v[i].xi>>v[i].y;
    sort(v+1,v+N+1 ,cmp) ;
    Answer = DEI(1,N);
    g.precision(7);
    g<<fixed<<sqrtl(Answer ) ;
}