Cod sursa(job #1946012)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 29 martie 2017 20:37:59
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

#define pii pair <int, int>
#define f first
#define s second

using namespace std;

pii v[100010];
vector <int> p;

long long dist (int st, int dr)
{
    return (1LL * (v[dr].f - v[st].f) * (v[dr].f - v[st].f) + 1LL * (v[dr].s - v[st].s) * (v[dr].s - v[st].s));
}

void del ()
{
    vector <int> aux;
    aux.swap (p);
}

long long divide (int st, int dr)
{
    if (dr - st + 1 <= 3)
    {
        if (dr - st + 1 == 2) return dist (st, dr);
        else return min (min (dist (st, st + 1), dist (st, st + 2)), dist (st + 1, st + 2));
    }

    int mij = (st + dr) >> 1;
    long long bst = min (divide (st, mij), divide (mij + 1, dr));

    del ();
    for (int i = st; i <= dr; ++i)
        if (dist (i, mij) <= bst) p.push_back (i);

    for (int i = 0; i < p.size (); ++i)
        for (int j = i + 1; j <= i + 7 && j < p.size (); ++j)
            bst = min (bst, dist (i, j));

    return bst;
}

int main ()
{
    freopen ("cmap.in", "r", stdin);
    freopen ("cmap.out", "w", stdout);

    int n;
    scanf ("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf ("%d %d", &v[i].f, &v[i].s);

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

    printf ("%.8f\n", sqrt (1LL * divide (1, n)));

    return 0;
}