Cod sursa(job #1253660)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 1 noiembrie 2014 16:55:14
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

#define x first
#define y second
#define NMAX 100007
#define INF 4e18
#define LL long long

using namespace std;

vector < pair <LL, LL> > V(NMAX), X, Y;

LL dist(const pair <LL, LL>& a, const pair <LL, LL>& b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

LL go(int st, int dr, vector < pair <LL, LL> >& X, vector < pair <LL, LL> >& Y) {
    if (st >= dr - 1)
        return INF;
    else
        if (dr - st == 2) {
            if (Y[st] > Y[st + 1])
                swap(Y[st], Y[st + 1]);
            return dist(X[st], X[st + 1]);
        }
    int mid = (st + dr) / 2;
    LL Ans = min(go(st, mid, X, Y), go(mid, dr, X, Y));
    merge(Y.begin() + st, Y.begin() + mid, Y.begin() + mid, Y.begin() + dr, V.begin());
    copy(V.begin(), V.begin() + (dr - st), Y.begin() + st);
    int v_size = 0;
    for (int i = st; i < dr; ++ i) if (abs(Y[i].y - X[mid].x) <= Ans)
        V[v_size ++] = Y[i];
    for (int i = 0; i < v_size - 1; ++ i) {
        for (int j = i + 1; j < v_size && j - i < 8; ++ j)
            Ans = min(Ans, dist(V[i], V[j]));
    }
    return Ans;
}

int main(void) {
    int n;
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    scanf("%d", &n);
    X.resize(n);
    Y.resize(n);
    for (int i = 0; i < (int) X.size(); ++ i)
        scanf("%d %d", &X[i].x, &X[i].y);
    sort(X.begin(), X.end());
    for (int i = 0; i < (int) X.size(); ++ i)
        Y[i] = make_pair(X[i].y, X[i].x);
    printf("%.6f", sqrt(go(0, (int) X.size(), X, Y)));
    return 0;
}