Cod sursa(job #986336)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 18 august 2013 15:31:07
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 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 long long square_distance (const point &a, const point &b) {

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

}

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

    if (l + 1 == r) {
        if (_P[l] > _P[r])
            swap (_P[l], _P[r]);
        return square_distance (P[l], P[r]);
    }
    if (l == r)
        return INF;
    int m = l + r >> 1, i, N = 0;
    long long p, q = min (divide (l, m), divide (m + 1, r));
    double k = sqrt (q);
    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) < k) {
            N = i++;
            break;
        }
    for (; i <= r; ++i)
        if (fabs (_P[i].y - P[m].x) < k) {
            p = square_distance (_P[N], _P[i]);
            if (p < q)
                q = p;
            N = i;
        }
    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", sqrt (divide (1, N)));

}