Cod sursa(job #1412816)

Utilizator oana28Oana Mitoiu oana28 Data 1 aprilie 2015 16:10:35
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
#define x first
#define y second
#define NMAX 100005
#define p(x,y) make_pair(x,y)
#define pairi pair <int,int>
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n,x,y;
pairi v[NMAX],aux[NMAX];
long long dist(pairi A, pairi B)
{
    int r=1LL*(A.x-B.x)*(A.x-B.x)+1LL*(A.y-B.y)*(A.y-B.y);
    return r;
}
void interclas(int st, int mij, int dr)
{
    int i,j,k=st;
    for (i=st,j=mij+1;i<=mij && j<=dr;)
        if (v[i].y<v[j].y) aux[k++]=v[i++];
        else aux[k++]=v[j++];
    for (;i<=mij;++i) aux[k++]=v[i];
    for (;j<=dr;++j) aux[k++]=v[j];
    for (i=st;i<=dr;++i)
        v[i]=aux[i];
}
long long distmin(int st, int dr)
{
    if (st+1==dr)
    {
        interclas(st,st,dr);
        return dist(v[st],v[dr]);
    }
    if (st+2==dr)
    {
        interclas(st,st,st+1);
        long long q=dist(v[st],v[st+1]);
        q=min(q,dist(v[st+1],v[dr]));
        interclas(st,st+1,dr);
        return q;
    }
    int mij=(st+dr)>>1;
    long long q1=distmin(st,mij);
    long long q2=distmin(mij+1,dr);
    interclas(st,mij,dr);
    long long minim=min(q1,q2);
    for (int i=st;i<dr;++i)
        for (int 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>>x>>y;
        v[i]=p(x,y);
    }
    fout<<setprecision(6)<<fixed<<sqrt((double)distmin(1,n))<<"\n";
    return 0;
}