Cod sursa(job #1662835)

Utilizator rocandu16Badulescu Dan Andrei rocandu16 Data 25 martie 2016 10:00:41
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

const int N = 100000;
const long long INF = 2000000000000000000LL;
const double eps = 0.000001;

struct punct
{
    int x, y;
};

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

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

void citire()
{
    in >> n;
    for (int i = 0; i < n; i++)
        in >> v[i].x >> v[i].y;
    in.close();
}

bool cmp(punct p, punct q)
{
    return p.x < q.x;
}

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

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);
}

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

long long calcul(int st, int dr, long long d)
{
    int nr, m = (st + dr) / 2, i, j, k, lim;
    punct mij = v[m];
    i = k = st;
    j = m + 1;
    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 = 0; i + 1 < nr; i++)
    {
        lim = i + 8;
        if (lim > nr)
            lim = nr;
        for (j = i + 1; j < lim; j++)
            d = min(d, distanta(aux[i], aux[j]));
    }
    return d;
}

long long apropiate(int st, int dr)
{
    if (st == dr)
        return INF;
    int m = (st + dr) / 2;
    long long r1, r2, r;
    r1 = apropiate(st, m);
    r2 = apropiate(m + 1, dr);
    r = min(r1, r2);
    return calcul(st, dr, r);
}

int main()
{
    citire();
    sort(v, v + n, cmp);
    out << fixed << setprecision(6) << sqrt(apropiate(0, n - 1)) << "\n";
    out.close();
    return 0;
}