Cod sursa(job #687640)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 22 februarie 2012 17:25:56
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

#define Infinity 2000000000
#define x first
#define y second
#define pdd pair <double, double>
#define NMax 100005

using namespace std;

int N;
pdd X[NMax], Y[NMax], Aux[NMax];

inline double Distance (pdd A, pdd B)
{
    return sqrt ((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

inline double Solve (int L, int R)
{
    if (L>=R) return Infinity;
    if (L+1==R)
    {
        sort (Y+L, Y+R+1);
        return Distance (X[L], X[R]);
    }
    int Mid=(L+R)/2;
    double DMin=min (Solve (L, Mid), Solve (Mid+1, R));
    merge (Y+L, Y+Mid+1, Y+Mid+1, Y+R+1, Aux);
    copy (Aux, Aux+R-L+1, Y+L);
    vector <pdd> P;
    for (int i=L; i<=R; ++i)
    {
        if (Y[i].y+DMin<=X[Mid].x and X[Mid].x<=Y[i].y-DMin)
        {
            P.push_back (Y[i]);
        }
    }
    for (int i=0; i<P.size (); ++i)
    {
        for (int j=i+1; j<P.size () and j-i<8; ++j)
        {
            DMin=min (DMin, Distance (P[i], P[j]));
        }
    }
    return DMin;
}

void Read ()
{
    freopen ("cmap.in", "r", stdin);
    scanf ("%d", &N);
    for (int i=1; i<=N; ++i)
    {
        scanf ("%lf %lf", &X[i].x, &X[i].y);
    }
    sort (X, X+N+1);
    for (int i=1; i<=N; ++i)
    {
        Y[i].x=X[i].y, Y[i].y=X[i].x;
    }
}

void Print ()
{
    freopen ("cmap.out", "w", stdout);
    printf ("%.6lf\n", Solve (1, N));
}

int main()
{
    Read ();
    Print ();
    return 0;
}