Cod sursa(job #980844)

Utilizator superman_01Avramescu Cristian superman_01 Data 5 august 2013 18:43:28
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<algorithm>
#define oo (4e18)
#define NMAX 100005
#include<cmath>
#define x first
#define y second
   
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
  typedef pair < int , int > point ;
pair < int , int > v[NMAX] ;
int N;
pair < int , int > pos[NMAX];
int k;
   
inline long long dist ( point A , point B )
{
    long long b = (A.x-B.x);
    b *= b;
    long long a =  ( A.y-B.y )    ;
    a *= a;
    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].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 ) ;
}