Cod sursa(job #1614155)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 25 februarie 2016 20:26:41
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 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((A.x-B.x)*(A.x-B.x)+(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)
                D=min(D, Distanta(a[i], a[j]));
        return D;
    }
    int m=(st+dr)/2;
    D=min(DI(st, m), DI(m, dr));
    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)
            D=min(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;
}