Cod sursa(job #1614187)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 25 februarie 2016 20:43:34
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

struct Punct
{   int x, y;
} a[100001];

int n, v[100001];

ifstream f("cmap.in");
ofstream g("cmap.out");

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

double Distanta(Punct A, Punct B)
{   return sqrt((double)(A.x-B.x)*(A.x-B.x)+(double)(A.y-B.y)*(A.y-B.y));
}

double DI(int st, int dr)
{   int i, j;
    double D=20000000000;
    if (dr-st<=3)
    {   for (i=st; i<dr; ++i)
            for (j=i+1; j<=dr; ++j)
                if (D>Distanta(a[i], a[j]))
                    D=Distanta(a[i], a[j]);
        return D;
    }
    int m=(st+dr)/2;
    double D1, D2;
    D1=DI(st, m);
    D2=DI(m, dr);
    if (D1<D)
        D=D1;
    if (D2<D)
        D=D2;
    int nr=0;
    for (i=m; i>=st && a[m].x-a[i].x<=D; --i)
        v[++nr]=i;
    for (i=m+1; i<=dr && a[i].x-a[m].x<=D; ++i)
        v[++nr]=i;
    sort(v+1, v+nr+1);
    for (i=1; i<=nr; ++i)
        for (j=i+1; j<=nr && j<=i+7; ++j)
            if (D>Distanta(a[v[i]], a[v[j]]))
                D=Distanta(a[v[i]], a[v[j]]);
    return D;
}

int main()
{   int i;
    f>>n;
    for (i=1; i<=n; ++i)
        f>>a[i].x>>a[i].y;
    sort(a+1, a+n+1, cmp);
    g<<fixed<<setprecision(6)<<DI(1, n);
    return 0;
}