Cod sursa(job #1379145)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 6 martie 2015 16:33:53
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

#define Point pair<int,int>
#define x first
#define y second

const int Nmax = 100000;

Point P[Nmax];
Point auxP[Nmax];
int N;

long long D(Point A, Point B)
{
    return 1LL * (A.x - B.x) * (A.x - B.x) + 1LL * (A.y - B.y) * (A.y - B.y);
}

bool cmp(Point A, Point B)
{
    return A.y < B.y;
}

long long dist(int st, int dr)
{
    if (st >= dr)
        return (1LL << 61);

    if (st + 1 == dr)
        return D(P[st], P[dr]);

    int m = (st + dr) / 2;

    long long d1 = dist(st, m);
    long long d2 = dist(m + 1, dr);
    long long  d = min(d1, d2);

    inplace_merge(P + st, P + m, P + dr, cmp);

    int nr = 0;

    for (int k = st; k <= dr; ++k)
        if ( abs(P[k].x - P[m].x) <= d )
            auxP[nr++] = P[k];

    for (int i = 0; i < nr; ++i)
    {
        int cnt = 8;
        int j = i - 1;

        while (j-- >= 0 && cnt-- > 0)
            d = min(d, D(auxP[i], auxP[j]));
    }

    return d;
}

int main()
{
    ifstream in("cmap.in");
    ofstream out("cmap.out");

    in >> N;

    for ( int i = 0; i < N; ++i )
        in >> P[i].x >> P[i].y;

    sort(P, P + N);

    out << fixed << setprecision(10);
    out << sqrt(dist(0, N - 1)) << "\n";

    return 0;
}