Cod sursa(job #701791)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 1 martie 2012 17:52:11
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define NMAX 100001
#define INF (1ll<<60)
using namespace std;
pair <int,int> p[NMAX];
int n,m,q[NMAX];
void read()
{
     int i;
     ifstream f("cmap.in");
     f>>n;
     for(i=1;i<=n;i++)
      f>>p[i].first>>p[i].second;
     f.close();
}
inline long long minim(long long a, long long b)
{
 if (a<b)
  return a;
 return b;
}
struct cmp
{
    bool operator () (const int &a,const int &b)
    {
        return p[a].second<p[b].second;
    }
};
inline long long distanta(pair <int,int> a, pair <int,int> b)
{
       return (long long)(a.first-b.first)*(a.first-b.first)+(long long)(a.second-b.second)*(a.second-b.second);
}
long long calc(int st, int dr)
{
     long long dist;
     int mij,i,j;
     if(dr-st<=2)
     {
      dist=INF;
      for(i=st;i<dr;i++)
       for(j=i+1;j<=dr;j++)
        dist=minim(dist,distanta(p[i],p[j]));
      return dist;
     }
     mij=(st+dr)/2;
     dist=minim(calc(st,mij),calc(mij+1,dr));
     m=0;
     for(i=st;i<=dr;i++)
      if(abs(p[i].second-p[mij].second)<=dist)
       q[++m]=i;
     sort(q+1,q+m+1,cmp());
     for(i=1;i<m;i++)
      for(j=i+1;j<=m && j-i<8;j++)
       dist=minim(dist,distanta(p[q[i]],p[q[j]]));
     return dist;
     
}
int main()
{
    ofstream g("cmap.out");
    read();
    sort(p+1,p+n+1);
    g<<fixed<<setprecision(6)<<sqrt(calc(1,n))<<"\n";
    g.close();
    return 0;
}