Cod sursa(job #984226)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 13 august 2013 20:49:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;

typedef pair <int, int> point;
const long long INF = 2e18;
const int NMAX = 100003;

point P[NMAX], _P[NMAX], K[NMAX];

inline double dist (const point &a, const point &b) {

    return sqrt ((b.x - a.x) * 1LL * (b.x - a.x) + (b.y - a.y) * 1LL * (b.y - a.y));

}

double divide (const int &l, const int &r) {

    if (l + 1 == r) {
        if (_P[l] > _P[r])
            swap (_P[l], _P[r]);
        return dist (P[l], P[r]);
    }
    if (l == r)
        return INF;
    int m = l + r >> 1, i, N = 0;
    double p, q = min (divide (l, m), divide (m + 1, r));
    merge (_P + l, _P + m + 1, _P + m + 1, _P + r + 1, K + 1);
    copy (K + 1, K + (r - l + 2), _P + l);
    for (i = l; i <= r; ++i)
        if (fabs (_P[i].y - P[m].x) < q)
            K[++N] = _P[i];
    for (i = 2; i <= N; ++i) {
        p = dist (K[i], K[i - 1]);
        if (p < q)
            q = p;
    }
    return q;
}

int main () {

    freopen ("cmap.in", "r", stdin);
    freopen ("cmap.out", "w", stdout);
    int N, i;
    scanf ("%d", &N);
    for (i = 1; i <= N; ++i)
        scanf ("%d%d", &P[i].x, &P[i].y);
    sort (P + 1, P + N + 1);
    for (i = 1; i <= N; ++i)
        _P[i] = make_pair (P[i].y, P[i].x);
    printf ("%.6lf", divide (1, N));

}