Cod sursa(job #473525)

Utilizator mlazariLazari Mihai mlazari Data 30 iulie 2010 00:30:25
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<iomanip>
#include<fstream>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

#define NMAX 100003

typedef long long ll;

ifstream fi("cmap.in");
ofstream fo("cmap.out");
vector < pair<ll,ll> > px,py,pv(NMAX);
int n,i;

ll distP(const pair<ll,ll> &p1, const pair<ll,ll> &p2) {
  return (p1.first-p2.first)*(p1.first-p2.first)+(p1.second-p2.second)*(p1.second-p2.second);
}

ll dmin(int l,int r) {
  ll best;
  int i,j;
  if(r-l<=2) {
    best=distP(px[l],px[l+1]);
    if(r-l==2) best=min(best,min(distP(px[l],px[r]),distP(px[l+1],px[r])));
    sort(py.begin()+l,py.begin()+r+1);
  }
  else {
    int mid=(l+r)/2;
    best=min(dmin(l,mid),dmin(mid+1,r));
    merge(py.begin()+l,py.begin()+mid+1,py.begin()+mid+1,py.begin()+r+1,pv.begin());
    copy(pv.begin(),pv.begin()+(r-l+1),py.begin()+l);
    int nv=0;
    for(i=l;i<=r;i++)
     if(abs(px[mid].first-py[i].second)<=best) pv[nv++]=py[i];
    for(i=0;i<nv-1;i++)
     for(j=i+1;j<=i+7 && j<nv;j++)
      best=min(best,distP(pv[i],pv[j]));
  }
  return best;
}

int main() {
  fi>>n;
  px.resize(n);
  py.resize(n);
  for(i=0;i<n;i++) fi>>px[i].first>>px[i].second;
  sort(px.begin(),px.end());
  for(i=0;i<=n;i++) py[i]=make_pair(px[i].second,px[i].first);
  fo<<fixed<<setprecision(7)<<sqrt(dmin(0,n-1))<<"\n";
  return 0;
}