Cod sursa(job #605585)

Utilizator SpiderManSimoiu Robert SpiderMan Data 1 august 2011 12:02:38
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
# include <algorithm>
# include <cstdio>
# include <cmath>
using namespace std;

# define x first
# define y second

typedef long long ll;
typedef pair <ll, ll> PR;
const char *FIN = "cmap.in", *FOU = "cmap.out";
const int MAX = 100005;
const ll oo = 4e18;

PR V[MAX], R[MAX], P[MAX];
int N;

ll dist (PR A, PR B) {
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

ll solve (int st, int dr) {
    if (dr - st == 1) return oo;
    if (dr - st == 2) {
        if (R[st] > R[st + 1]) swap (R[st], R[st + 1]);
        return dist (R[st], R[st + 1]);
    }
    int mij = st + dr >> 1;
    ll sol = min (solve (st, mij), solve (mij, dr));

    merge (R + st, R + mij, R + mij, R + dr, P);
    copy (P, P + (dr - st), R + st);

    int mare = -1;
    for (int i = st; i < dr; ++i)
        if (abs (R[i].y - P[mij].x) <= sol)
            V[++mare] = R[i];
    for (int i = 0; i < mare; ++i)
        for (int j = i + 1; j < mare && j - i < 8; ++j)
            sol = min (sol, dist (V[i], V[j]));
    return sol;
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf ("%lld %lld", &P[i].x, &P[i].y);
    sort (P, P + N);
    for (int i = 0; i < N; ++i)
        R[i] = make_pair (P[i].y, P[i].x);
    fprintf (fopen (FOU, "w"), "%.6lf", sqrt (solve (0, N)));
}