Cod sursa(job #1214758)

Utilizator acomAndrei Comaneci acom Data 31 iulie 2014 12:11:57
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
#define NMAX 100005
ifstream fin("cmap.in");
ofstream fout("cmap.out");
pair <long long,long long> v[NMAX],aux[NMAX];
int n;
double dist(pair <long long,long long> A, pair <long long,long long> B)
{
    double X=(A.first-B.first)*(A.first-B.first);
    double Y=(A.second-B.second)*(A.second-B.second);
    return sqrt(X+Y);
}

void interclasare(int st, int m, int dr)
{
    int i,j,k;
    for (i=st,j=m+1,k=st-1;i<=m && j<=dr;)
        if (v[i].second<v[j].second)
            aux[++k]=v[i++];
        else
            aux[++k]=v[j++];
    for (;i<=m;++i)
        aux[++k]=v[i];
    for (;j<=dr;++j)
        aux[++k]=v[j];
    for (i=st;i<=dr;++i)
        v[i]=aux[i];
}
double rec(int st, int dr)
{
    int i,j;
    double minim;
    if (dr-st==1)
    {
        interclasare(st,st,dr);
        return dist(v[st],v[dr]);
    }

    if (dr-st==2)
    {
        minim=min(dist(v[st],v[st+1]),dist(v[st],v[dr]));
        minim=min(minim,dist(v[dr],v[st+1]));
        interclasare(st,st+1,dr);
        return minim;
    }
    int m=(st+dr)>>1;
    double qs=rec(st,m);
    double qd=rec(m+1,dr);
    interclasare(st,m,dr);
    minim=min(qs,qd);
    for (i=st;i<=dr;++i)
        for (j=i+1;j<=i+7 && j<=dr;++j)
            minim=min(minim,dist(v[i],v[j]));
    return minim;
}
int main()
{
    int i;
    fin>>n;
    for (i=1;i<=n;++i)
        fin>>v[i].first>>v[i].second;
    sort(v+1,v+n+1);
    fout<<setprecision(6)<<fixed<<rec(1,n)<<"\n";
    return 0;
}