Cod sursa(job #1273780)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 22 noiembrie 2014 22:27:21
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

const int NMAX=100005;

#define x first
#define y second

typedef pair<int,int> punct;

double dist(punct A, punct B)
{
    double dx=A.x-B.x, dy=A.y-B.y;
    return sqrt(dx*dx + dy*dy);
}

punct P[NMAX],Y[NMAX],Z[NMAX];

double solve(int l,int r)
{
    if (r-l+1 <= 3)
    {
        double dmin=1e10;
        for (int i=l; i<r; ++i)
            for (int j=i+1; j<=r; ++j)
                dmin=min(dmin, dist(P[i], P[j]));
        sort(Y+l,Y+r+1);
        return dmin;
    }

    int m=(l+r)/2, i, j, len=0;
    double dmin=min(solve(l,m), solve(m+1,r));
    merge(Y+l,Y+m+1,Y+m+1,Y+r+1,Z);
    copy(Z,Z+r-l+1,Y+l);
    for (i=l; i<=r; ++i)
        if (abs(Y[i].y - P[m].x) <= dmin)
            Z[++len]=Y[i];

    for (i=2; i<=len; ++i)
        for (j=i-1; j>=1 && i-j<=7; --j)
            dmin=min(dmin, dist(Z[i], Z[j]));

    return dmin;
}

int N;

int main()
{
    ifstream f("cmap.in");
    ofstream g("cmap.out");
    int i;
    f>>N;
    for (i=1; i<=N; ++i)
        f>>P[i].x>>P[i].y;
    sort(P+1,P+N+1);
    for (i=1; i<=N; ++i)
        Y[i]=make_pair(P[i].y, P[i].x);

    g<<setprecision(6)<<fixed<<solve(1,N)<<"\n";
    f.close();
    g.close();
    return 0;
}