Cod sursa(job #1273767)

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

#define x first
#define y second
#define INF 1000000000ll
#define NMax 100005

int N;
typedef pair<int,int> punct;
punct P[NMax],Y[NMax],Z[NMax];

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

double solve(int st, int dr)
{
    if (dr-st <= 2)
    {
        double dmin=INF;
        for (int i=st; i<dr; ++i)
            for (int j=i+1; j<=dr; ++j)
                dmin=min(dmin, dist(P[i], P[j]));
        sort(Y+st, Y+dr+1);
        return dmin;
    }

    int m=(st+dr)/2, len=0, i, j;
    //calculez distanta minima in cele doua semiplane
    double dmin = min(solve(st, m), solve(m+1, dr));
    merge(Y+st, Y+m+1, Y+m+1, Y+dr+1, Z);
    copy(Z, Z+dr-st+1, Y+st);

    for (i=st; i<=dr; 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 main()
{
    ifstream f("cmap.in");
    ofstream g("punc.out");
    int i;
    f>>N;
    for (i=1; i<=N; i++)
        f>>P[i].x>>P[i].y;
    //sortez punctele dupa x, si la egalitate dupa 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);
    f.close();
    g.close();
    return 0;
}