Cod sursa(job #980873)

Utilizator superman_01Avramescu Cristian superman_01 Data 5 august 2013 19:52:36
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<utility>
#define NMAX 100005
#include<cmath>
   
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
typedef pair < int , int > point ;
point v[NMAX] ;
int N;
const double oo ( 1<<30);


inline double dist ( point A , point B )
{
	return sqrt ( ( long long )( A.first-B.first) * (A.first-B.first ) + (long long) ( A.second-B.second) *( A.second-B.second));
}
  
bool comp ( point A , point B )
{
    return A.second < B.second;
}
double DEI (int st , int dr)
{
    if (st >= dr)
        return oo;
    if (st == dr- 1)
    {
        if (v[st].second > v[dr].second)
            swap(v[st],v[dr]);
        return dist(v[st],v[dr]);
    }
    int m((st + dr) >> 1);
    double x( min(DEI(st,m),DEI(m + 1,dr)) );
    vector<point> pos;
    int i;
    for (i = st ; i <= dr ; ++i)
        if (i != m)
            if (abs(v[m].first - v[i].first) < x)
                pos.push_back(v[i]);
    int j, end;
    sort(pos.begin(),pos.end(), comp);
    for (i = 0 ; i < pos.size() ; ++i)
        for (j = i + 1 ; j <= i + 8 && j < pos.size() ; ++j)
            x = min(x,dist(pos[i],pos[j]));
    return x;
	}

int main ( void )
{
    int i ;
    double Answer = oo ;
    f>>N;
	for( i = 1 ; i <= N ;  ++i )
        f>>v[i].first>>v[i].second;
    sort(v+1,v+N+1 ) ;
    Answer = DEI(1,N);
    g.precision(7);
    g<<fixed<<Answer ;
}