Cod sursa(job #1071077)

Utilizator RamaStanciu Mara Rama Data 2 ianuarie 2014 15:43:39
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define Nmax 100010
#define INF 1000000010

using namespace std;

struct punct
{
    long long x, y;
} Px[Nmax], Py[Nmax];

int n;
long long i, Ny, mij, p, j;
int poz[Nmax];

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

double 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 ()
{

    ifstream in("cmap.in");
    ofstream out("cmap.out");

    in>>n;
    for (i = 1; i <= n; i++)
     {
        in>>Px[i].x>>Px[i].y;
        poz[i] = i;
    }

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

    cout<<setprecision(8)<<Dmin (1, n);

    return 0;
}