Cod sursa(job #1662368)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 24 martie 2016 18:36:30
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>

using namespace std;

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

#define N 100001
#define INF 9223372036854775807

struct punct
{
    int x, y;
};

int n;
punct v[N], aux[N];

inline bool compara(punct p1, punct p2)
{
    return p1.x < p2.x;
}

inline long long minim(long long a, long long b)
{
    return a < b ? a : b;
}

inline int modul(int x)
{
    return x > 0 ? x : -x;
}

inline long long distanta(punct p1, punct p2)
{
    return (long long)(p1.x - p2.x) * (p1.x - p2.x) + (long long)(p1.y - p2.y) * (p1.y - p2.y);
}

inline long long calcul(int st, int dr, long long d)
{
    int nr = 0, m = (st + dr) >> 1, i, j, k;
    i = st;
    k = st;
    j = m + 1;
    punct mij = v[m];
    while(i <= m && j <= dr)
        if(v[i].y < v[j].y)
            aux[k++] = v[i++];
        else
            aux[k++] = v[j++];
    while(i <= m)
        aux[k++] = v[i++];
    while(j <= dr)
        aux[k++] = v[j++];
    nr = 0;
    for(i = st; i <= dr; i++)
    {
        v[i] = aux[i];
        if(modul(v[i].x - mij.x) <= d)
            aux[++nr] = aux[i];
    }
    for(i = 1; i <= nr; i++)
    {
        int lim = i + 7;
        if(lim > nr)
            lim = nr;
        for(j = i + 1; j <= lim; j++)
            d = minim(d, distanta(aux[i], aux[j]));
    }
    return d;
}

long long divideEtImpera(int st, int dr)
{
    if(st == dr)
        return INF;
    int m = (st + dr) >> 1;
    long long d1, d2, d;
    d1 = divideEtImpera(st, m);
    d2 = divideEtImpera(m + 1, dr);
    d = minim(d1, d2);
    return calcul(st, dr, d);
}

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

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

    out << fixed << setprecision(6) << sqrt(divideEtImpera(1, n)) << '\n';
    return 0;
}