Cod sursa(job #1107575)

Utilizator TeofilosTeofil Teofilos Data 13 februarie 2014 23:02:18
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <cstdio>
#include <algorithm>
#include <math.h>
using namespace std;

#define Nmax 100010
#define INF 1000000010

struct punct {int x, y;} Px[Nmax], Py[Nmax];
int n, i, Ny, mij, p, j;
int poz[Nmax];

int cmp_x (int a, int b) {
    return Px[a].x < Px[b].x;
}

int cmp_y (punct a, punct b) {
    return a.y < b.y;
}

double dist (double x1, double y1, double x2, double y2) {
    return sqrt ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double Dmin (int st, int dr) {

    double dmin = INF, d;
    if (dr - st + 1 <= 3) {
        if (dr - st + 1 >= 2)
            dmin = dist ( Px[ poz[st] ].x, Px[ poz[st] ].y, Px[ poz[st + 1] ].x, Px[ poz[st + 1] ].y );

        if (dr - st + 1 == 3) {
            d = dist ( Px[ poz[st] ].x, Px[ poz[st] ].y, Px[ poz[st + 2] ].x, Px[ poz[st + 2] ].y );
            if (d < dmin) dmin = d;

            d = dist ( Px[ poz[st + 2] ].x, Px[ poz[st + 2] ].y, Px[ poz[st + 1] ].x, Px[ poz[st + 1] ].y );
            if (d < dmin) dmin = d;
        }

        return dmin;
    }

    dmin = Dmin (st, (dr + st) >> 1);
    d = Dmin (((dr + st) >> 1) + 1, dr);
    if (d < dmin) dmin = d;

    mij = (st + dr) >> 1; Ny = 0;
    for (i = st; i <= dr; i++)
        if ( abs (Px[poz[mij]].x - Px[poz[i]].x) <= dmin )
            Py[++Ny] = Px[poz[i]];

    sort (Py + 1, Py + Ny + 1, cmp_y);
    for (i = 2, p = 1; i <= Ny; i++) {
        while (Py[i].y - Py[p].y > dmin)
            p++;

        for (j = p; j < i; j++) {
            d = dist (Py[i].x, Py[i].y, Py[j].x, Py[j].y);
            if (d < dmin) dmin = d;
        }
    }

    return dmin;
}

int main () {

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

    scanf ("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf ("%d %d", &Px[i].x, &Px[i].y);
        poz[i] = i;
    }

    sort (poz + 1, poz + n + 1, cmp_x);

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

    return 0;
}