Cod sursa(job #781525)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 24 august 2012 16:35:20
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;
int n;
double sol,infinit=100000000000000001.0;
typedef pair<double,double> Punct;
Punct X[100100],Y[100100],Z[100100];
Punct v[100100];
inline void Citire(){
   int i;
    freopen("cmap.in","r",stdin);
     scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%lf %lf",&X[i].first,&X[i].second);
}
inline double Dist(Punct A,Punct B){
    return sqrt((A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second));
}
inline double Divide_et_Impera(int st,int dr){
   if(st>=dr-1)return infinit;
   else if(dr-st==2){
      sort(Y+st,Y+dr);
       return Dist(X[st],X[st+1]);
       }
    int mij=(st+dr)/2,i,j,size;
    double distanta=min(Divide_et_Impera(st,mij),Divide_et_Impera(mij,dr));
    merge(Y+st,Y+mij,Y+mij,Y+dr,Z);
    copy(Z,Z+dr-st,Y+st);
     size=0;
    for(i=st;i<dr;i++){
     if(abs(Y[i].second-X[mij].first)<=distanta)
       v[size++]=Y[i];
      }
    for(i=0;i<size;i++)
     for(j=i+1;j<size && j-i<8;j++)distanta=min(distanta,Dist(v[i],v[j]));
   return distanta;
}
inline void Rezolvare(){
   int i;
    sort(X,X+n);
   for(i=0;i<n;i++)Y[i]=make_pair(X[i].second,X[i].first);
    sol=Divide_et_Impera(0,n);
}
inline void Afisare(){
    freopen("cmap.out","w",stdout);
     printf("%.6lf\n",sol);
}
int main(){
   Citire();
    Rezolvare();
   Afisare();
  return 0;
}