Cod sursa(job #871137)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 4 februarie 2013 15:16:29
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include<fstream>
using namespace std;
#include<vector>
#include<utility>
#include<iomanip>
#include<algorithm>
#include<cmath>
#define INF 100000
ifstream cin("cmap.in");
ofstream cout("cmap.out");
typedef pair<double,double> punct;
typedef vector< punct > vp;
typedef vp::iterator vpit;

vp P; //vectorul punctelor din plan
//functia de comparare a absciselor (pentru sortare)
bool lessx(punct p1, punct p2){
     return p1.first<p2.first;
     };
//calculul distantei intre doua puncte
double dist(punct p1, punct p2){
       return sqrt((p2.first-p1.first)*(p2.first-p1.first)+(p2.second-p1.second)*(p2.second-p1.second));
       };
//selecteaza in R punctele din P situate inm banda
// (xmed-d. xmed+d)
void selx(vpit l, vpit r, double d, double xmed, vp& R){
     for(vpit i=l; i!=r+1; i++)
              if(fabs((*i).first-xmed)<d) R.push_back(*i);
              };
//determina distanta minima intre 2 puncte R considerand 
//cel mult 7 puncte
double sely(const vp& R, double d){
                  int n=R.size();
                  double dm=d;
                  for(int j=0;j<n;j++)
                          for(int k=j+1; k<min(n, j+7); k++)
                                 { punct p1=R[j];
                                  punct p2=R[k];
                                  dm=min(dm, dist(p1, p2));
                                  }
                  return dm;
                  };
double dMin(vpit l, vpit r)
{      double d;
       if(l==r)
               d=INF;
       else
       { 
           vpit m=l+(r-l)/2;
           double dl=dMin(l, m);
           double dr=dMin(m+1, r);
           d=min(dl,dr);
           inplace_merge(l, m, r);
           vp R;
           selx(l, r, d, (*m).first, R);
           d=sely(R, d);
}
return d;
};
int main ()
{
    
    int n;
    cin>>n;
    P.resize(n);
    for(int i=0;i<n;i++)
        cin>>P[i].first>>P[i].second;
    sort(P.begin(), P.end());
    double d=dMin(P.begin(), P.end());
    cout<<fixed<<setprecision(6)<<d<<endl;
  //  system("pause");
    return 0;
}