Cod sursa(job #985216)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 16 august 2013 22:19:39
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <cmath>

#define maxn 100001
#define x first
#define y second
#define inf 1<<30

using namespace std;

ifstream fin ("cmap.in");
ofstream fout ("cmap.out");

typedef pair <double,double>  point;
point v[maxn],aux[maxn],test[maxn];
int n;

inline bool cmp1 (const point &a, const point &b)
{
    if (a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

inline bool cmp2 (const point &a, const point &b)
{
    if (a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}

inline double dist (const point &A, const point &B)
{
    return sqrt ((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}

double closest_pair (int p, int q)
{
    if (p==q) return inf;
    if (p+1==q)
    {
        if (v[q].y<v[p].y) swap (v[p],v[q]);
        return dist (v[p],v[q]);
    }

    int mid = (p+q)/2; double echelon = v[mid].x;
    double D1 = closest_pair (p,mid);
    double D2 = closest_pair (mid+1,q);
    double D = min (D1,D2);
     int t=0;

    merge (v+p,v+mid+1,v+mid+1,v+q+1,aux+p,cmp2);

    for (int i=p; i<=q ; ++i)
        if (fabs(aux[i].x-echelon) < D) test[++t]=aux[i];

    for (int i=1; i<=t; ++i)
      for (int j=i+1; j<=i+7 && j<=t; ++j)
          D = min (D,dist(test[i],test[j]) );

    for (int i=p; i<=q; ++i) v[i]=aux[i];

    return D;
}

int main()
{
     fin>>n;
     for (int i=1; i<=n; ++i) fin>>v[i].x>>v[i].y;

     sort (v+1, v+n+1, cmp1);

     double D = closest_pair (1,n);
     fout<<fixed<<setprecision(7)<<D;
}