Cod sursa(job #579811)

Utilizator bixcabc abc bixc Data 12 aprilie 2011 14:52:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
using namespace std;

#define Nmax 100010

struct punct {
    int x, y;
} P[Nmax];

int n;
int Poz[Nmax];

double dist (int a, int b) {

    return sqrt( (long double) ((long long)(P[a].x - P[b].x) * (long long)(P[a].x - P[b].x) + (long long)(P[a].y - P[b].y) * (long long)(P[a].y - P[b].y)));
}

inline double Min (double a, double b) {
    if (a < b) return a;
    return b;
}

bool cmp (const int &a, const int &b) {

    return P[a].y < P[b].y;
}

bool cmpx (const punct &a, const punct &b) {

    return a.x < b.x;
}

double Cmap (int st, int dr) {

    if (st == dr) return 0;

    double dmin;
    if (dr - st + 1 <= 3) {
        dmin = dist (st, st + 1);
        if (st + 2 == dr) {
            dmin = Min (dmin, dist (st + 1, st + 2) );
            dmin = Min (dmin, dist (st, st + 2) );
        }

        return dmin;
    }

    dmin = Min ( Cmap (st, ((st + dr) >> 1)), Cmap (((st + dr) >> 1) + 1, dr) );

    int i, j, N = 0, mij = ((st + dr) >> 1), p;
    double d2;
    for (i = st; i <= dr; i++)
        if ( abs (P[i].x - P[mij].x) <= dmin )
            Poz[++N] = i;

    sort (Poz + 1, Poz + N + 1, cmp);
    for (i = 2, p = 1; i <= N; i++) {
        while ( P[ Poz[i] ].y - P[ Poz[p] ].y >= dmin ) p++;

        for (j = p; j < i; j++)
            dmin = min (dmin, dist (Poz[j], Poz[i]) );
    }

    return dmin;
}

int main () {

    freopen ("cmap.in", "r", stdin);
    freopen ("cmap.out", "w", stdout);

    scanf ("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf ("%d %d", &P[i].x, &P[i].y);

    sort (P + 1, P + n + 1, cmpx);

    printf ("%.6lf\n", Cmap (1, n));

    return 0;
}